SherbyNet - /page/wikibook/entry.mu

Micron Document

<!DOCTYPE html>

<title>Multidimensional discrete convolution</title>

</head>

Multidimensional discrete convolution

</h1>

</header>

In signal processing, multidimensional discrete convolution refers to the mathematical operation between two functions f and g on an n-dimensional lattice that produces a third function, also of n-dimensions. Multidimensional discrete convolution is the discrete analog of the <a href="Convolution#Domain_of_definition" title="Convolution">multidimensional convolution</a> of functions on <a href="Euclidean_space" title="Euclidean space">Euclidean space</a>. It is also a special case of <a href="Convolution#Convolutions_on_groups" title="Convolution">convolution on groups</a> when the <a href="Group_(mathematics)" title="Group (mathematics)">group</a> is the group of n-tuples of integers.

<div class="mw-heading mw-heading2"><h2 id="Definition">Definition</h2></div>

<div class="mw-heading mw-heading3"><h3 id="Problem_statement_and_basics">Problem statement and basics</h3></div>

Similar to the one-dimensional case, an asterisk is used to represent the convolution operation. The number of dimensions in the given operation is reflected in the number of asterisks. For example, an M-dimensional convolution would be written with M asterisks. The following represents a M-dimensional convolution of discrete signals:

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<mover>

</mover>

</mrow>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y(n_{1},n_{2},...,n_{M})=x(n_{1},n_{2},...,n_{M})*{\overset {M}{\cdots }}*h(n_{1},n_{2},...,n_{M})}</annotation>

</semantics>

</math><img src="./528dc47612f672eb783f8ddc9f87bcaaad16dfc9.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:62.829ex; height:3.676ex;" alt="{\displaystyle y(n_{1},n_{2},...,n_{M})=x(n_{1},n_{2},...,n_{M})*{\overset {M}{\cdots }}*h(n_{1},n_{2},...,n_{M})}" loading="lazy">

For discrete-valued signals, this convolution can be directly computed via the following:

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</munderover>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</munderover>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</munderover>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \sum _{k_{1}=-\infty }^{\infty }\sum _{k_{2}=-\infty }^{\infty }...\sum _{k_{M}=-\infty }^{\infty }h(k_{1},k_{2},...,k_{M})x(n_{1}-k_{1},n_{2}-k_{2},...,n_{M}-k_{M})}</annotation>

</semantics>

</math><img src="./a9b040c7581bf2a9d9a97714d6018a634396308b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.338ex; width:73.146ex; height:7.176ex;" alt="{\displaystyle \sum _{k_{1}=-\infty }^{\infty }\sum _{k_{2}=-\infty }^{\infty }...\sum _{k_{M}=-\infty }^{\infty }h(k_{1},k_{2},...,k_{M})x(n_{1}-k_{1},n_{2}-k_{2},...,n_{M}-k_{M})}" loading="lazy">

The resulting output region of support of a discrete multidimensional convolution will be determined based on the size and regions of support of the two input signals.

Listed are several properties of the two-dimensional convolution operator. Note that these can also be extended for signals of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle N}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle N}</annotation>

</semantics>

Commutative Property:

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x**h=h**x}</annotation>

</semantics>

</math><img src="./b2441c28f180d910f4b515e965ccf6cc03ad17b0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:15.15ex; height:2.176ex;" alt="{\displaystyle x**h=h**x}" loading="lazy">

Associate Property:

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (x**h)**g=x**(h**g)}</annotation>

</semantics>

</math><img src="./40f98417a5b5c94388b60626c5f26782862dd318.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:27.715ex; height:2.843ex;" alt="{\displaystyle (x**h)**g=x**(h**g)}" loading="lazy">

Distributive Property:

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x**(h+g)=(x**h)+(x**g)}</annotation>

</semantics>

</math><img src="./72c6b07f4d114d095e9a6e69c4201a4d01c57fbf.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:33.178ex; height:2.843ex;" alt="{\displaystyle x**(h+g)=(x**h)+(x**g)}" loading="lazy">

These properties are seen in use in the figure below. Given some input <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x(n_{1},n_{2})}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x(n_{1},n_{2})}</annotation>

</semantics>

</math><img src="./85ed8c47c0c37801b032df0db40fa6de35109737.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.071ex; height:2.843ex;" alt="{\displaystyle x(n_{1},n_{2})}" loading="lazy"> that goes into a filter with impulse response <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle h(n_{1},n_{2})}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle h(n_{1},n_{2})}</annotation>

</semantics>

</math><img src="./3af74de774e14e28f2377ea93aa13ed591296300.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.08ex; height:2.843ex;" alt="{\displaystyle h(n_{1},n_{2})}" loading="lazy"> and then another filter with impulse response <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle g(n_{1},n_{2})}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle g(n_{1},n_{2})}</annotation>

</semantics>

</math><img src="./fa8e45b7ad89eb84b134ab892ec2fad905b0bc16.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.857ex; height:2.843ex;" alt="{\displaystyle g(n_{1},n_{2})}" loading="lazy">, the output is given by <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle y(n_{1},n_{2})}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y(n_{1},n_{2})}</annotation>

</semantics>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle w(n_{1},n_{2})}</annotation>

</semantics>

</math><img src="./6dbb80ddb7469b5f4890d470ef908ccc2df07fef.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.405ex; height:2.843ex;" alt="{\displaystyle w(n_{1},n_{2})}" loading="lazy">, this means that:

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle w=x**h}</annotation>

</semantics>

</math><img src="./2af710582af94e3c30a0140b890a77d5e485f0df.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:10.788ex; height:2.176ex;" alt="{\displaystyle w=x**h}" loading="lazy">

Further, that intermediate function is then convolved with the impulse response of the second filter, and thus the output can be represented by:

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y=w**g=(x**h)**g}</annotation>

</semantics>

</math><img src="./b2ed469eb60f0d2dab917684ba3d128e47658fae.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:25.798ex; height:2.843ex;" alt="{\displaystyle y=w**g=(x**h)**g}" loading="lazy">

Using the associative property, this can be rewritten as follows:

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y=x**(h**g)}</annotation>

</semantics>

</math><img src="./93e7309031b90d2cb31c340800f014fd7a3d29df.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:16.562ex; height:2.843ex;" alt="{\displaystyle y=x**(h**g)}" loading="lazy">

meaning that the equivalent impulse response for a cascaded system is given by:

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle h_{eq}=h**g}</annotation>

</semantics>

</math><img src="./438a8047d85c37f678226eb8b02fedb8dd8ce2d0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:12.004ex; height:2.843ex;" alt="{\displaystyle h_{eq}=h**g}" loading="lazy">

A similar analysis can be done on a set of parallel systems illustrated below.

In this case, it is clear that:

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y=(x**h)+(x**g)}</annotation>

</semantics>

</math><img src="./9e2eb3288942964ea59e420f502945d645b5b3f6.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:22.542ex; height:2.843ex;" alt="{\displaystyle y=(x**h)+(x**g)}" loading="lazy">

Using the distributive law, it is demonstrated that:

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y=x**(h+g)}</annotation>

</semantics>

</math><img src="./10db12c1ff41ca853fb59441866654a9a0985b67.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:16.045ex; height:2.843ex;" alt="{\displaystyle y=x**(h+g)}" loading="lazy">

This means that in the case of a parallel system, the equivalent impulse response is provided by:

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle h_{eq}=h+g}</annotation>

</semantics>

</math><img src="./491560248920a70a0d659c4ae1605a03d2676102.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:11.487ex; height:2.843ex;" alt="{\displaystyle h_{eq}=h+g}" loading="lazy">

The equivalent impulse responses in both cascaded systems and parallel systems can be generalized to systems with <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle N}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle N}</annotation>

</semantics>

</math><img src="./f5e3890c981ae85503089652feb48b191b57aae3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.064ex; height:2.176ex;" alt="{\displaystyle N}" loading="lazy">-number of filters.<a href="#cite_note-:4-1">[1]</a>

<div class="mw-heading mw-heading3"><h3 id="Motivation_and_applications">Motivation and applications</h3></div>

Convolution in one dimension was a powerful discovery that allowed the input and output of a linear shift-invariant (LSI) system (see <a href="LTI_system_theory" class="mw-redirect" title="LTI system theory">LTI system theory</a>) to be easily compared so long as the impulse response of the filter system was known. This notion carries over to multidimensional convolution as well, as simply knowing the impulse response of a multidimensional filter too allows for a direct comparison to be made between the input and output of a system. This is profound since several of the signals that are transferred in the digital world today are of multiple dimensions including images and videos. Similar to the one-dimensional convolution, the multidimensional convolution allows the computation of the output of an LSI system for a given input signal.

For example, consider an image that is sent over some wireless network subject to electro-optical noise. Possible noise sources include errors in channel transmission, the analog to digital converter, and the <a href="Image_sensor" title="Image sensor">image sensor</a>. Usually noise caused by the channel or sensor creates spatially-independent, high-frequency signal components that translates to arbitrary light and dark spots on the actual image. In order to rid the image data of the high-frequency spectral content, it can be multiplied by the frequency response of a low-pass filter, which based on the convolution theorem, is equivalent to convolving the signal in the time/spatial domain by the impulse response of the low-pass filter. Several impulse responses that do so are shown below.<a href="#cite_note-2">[2]</a>

In addition to filtering out spectral content, the multidimensional convolution can implement <a href="Edge_detection" title="Edge detection">edge detection</a> and smoothing. This once again is wholly dependent on the values of the impulse response that is used to convolve with the input image. Typical impulse responses for edge detection are illustrated below.

In addition to image processing, multidimensional convolution can be implemented to enable a variety of other applications. Since filters are widespread in digital communication systems, any system that must transmit multidimensional data is assisted by filtering techniques It is used in real-time video processing, neural network analysis, digital geophysical data analysis, and much more.<a href="#cite_note-3">[3]</a>

One typical distortion that occurs during image and video capture or transmission applications is blur that is caused by a low-pass filtering process. The introduced blur can be modeled using Gaussian low-pass filtering.

<div class="mw-heading mw-heading2"><h2 id="Row-column_decomposition_with_separable_signals">Row-column decomposition with separable signals</h2></div>

<div class="mw-heading mw-heading3"><h3 id="Separable_signals">Separable signals</h3></div>

A signal is said to be separable if it can be written as the product of multiple one-dimensional signals.<a href="#cite_note-:4-1">[1]</a> Mathematically, this is expressed as the following:

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x(n_{1},n_{2},...,n_{M})=x(n_{1})x(n_{2})...x(n_{M})}</annotation>

</semantics>

</math><img src="./fb8a9104ce330959ce37d21e94868d9ebba9a61c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:41.463ex; height:2.843ex;" alt="{\displaystyle x(n_{1},n_{2},...,n_{M})=x(n_{1})x(n_{2})...x(n_{M})}" loading="lazy">

Some readily recognizable separable signals include the unit step function, and the dirac-delta impulse function.

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle u(n_{1},n_{2},...,n_{M})=u(n_{1})u(n_{2})...u(n_{M})}</annotation>

</semantics>

</math><img src="./f215ff18e73d8cd0e30de350042fff774c996ea2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:41.463ex; height:2.843ex;" alt="{\displaystyle u(n_{1},n_{2},...,n_{M})=u(n_{1})u(n_{2})...u(n_{M})}" loading="lazy"> (unit step function)

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \delta (n_{1},n_{2},...,n_{M})=\delta (n_{1})\delta (n_{2})...\delta (n_{M})}</annotation>

</semantics>

</math><img src="./c4dcef98d6f4b8cfb6187a0600127baa108f8d4a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:40.339ex; height:2.843ex;" alt="{\displaystyle \delta (n_{1},n_{2},...,n_{M})=\delta (n_{1})\delta (n_{2})...\delta (n_{M})}" loading="lazy"> (dirac-delta impulse function)

Convolution is a linear operation. It then follows that the multidimensional convolution of separable signals can be expressed as the product of many one-dimensional convolutions. For example, consider the case where x and h are both separable functions.

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</munderover>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</munderover>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x(n_{1},n_{2})**h(n_{1},n_{2})=\sum _{k_{1}=-\infty }^{\infty }\sum _{k_{2}=-\infty }^{\infty }h(k_{1},k_{2})x(n_{1}-k_{1},n_{2}-k_{2})}</annotation>

</semantics>

</math><img src="./f3a9d9d1f37978dcfa131857cb3be0158555c50c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.338ex; width:65.153ex; height:7.176ex;" alt="{\displaystyle x(n_{1},n_{2})**h(n_{1},n_{2})=\sum _{k_{1}=-\infty }^{\infty }\sum _{k_{2}=-\infty }^{\infty }h(k_{1},k_{2})x(n_{1}-k_{1},n_{2}-k_{2})}" loading="lazy">

By applying the properties of separability, this can then be rewritten as the following:

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</munderover>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</munderover>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x(n_{1},n_{2})**h(n_{1},n_{2})={\bigg (}\sum _{k_{1}=-\infty }^{\infty }h(k_{1})x(n_{1}-k_{1}){\bigg )}{\bigg (}\sum _{k_{2}=-\infty }^{\infty }h(k_{2})x(n_{2}-k_{2}){\bigg )}}</annotation>

</semantics>

</math><img src="./45045c50bf8f67ce8e39bc845e0f96de117c8818.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.338ex; width:76.989ex; height:7.176ex;" alt="{\displaystyle x(n_{1},n_{2})**h(n_{1},n_{2})={\bigg (}\sum _{k_{1}=-\infty }^{\infty }h(k_{1})x(n_{1}-k_{1}){\bigg )}{\bigg (}\sum _{k_{2}=-\infty }^{\infty }h(k_{2})x(n_{2}-k_{2}){\bigg )}}" loading="lazy">

It is readily seen then that this reduces to the product of one-dimensional convolutions:

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x(n_{1},n_{2})**h(n_{1},n_{2})={\bigg [}x(n_{1})*h(n_{1}){\bigg ]}{\bigg [}x(n_{2})*h(n_{2}){\bigg ]}}</annotation>

</semantics>

</math><img src="./f71c141b786fcce579b75251e82759f9cf61ec26.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.505ex; width:56.276ex; height:6.176ex;" alt="{\displaystyle x(n_{1},n_{2})**h(n_{1},n_{2})={\bigg [}x(n_{1})*h(n_{1}){\bigg ]}{\bigg [}x(n_{2})*h(n_{2}){\bigg ]}}" loading="lazy">

This conclusion can then be extended to the convolution of two separable M-dimensional signals as follows:

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<mover>

</mover>

</mrow>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x(n_{1},n_{2},...,n_{M})*{\overset {M}{\cdots }}*h(n_{1},n_{2},...,n_{M})={\bigg [}x(n_{1})*h(n_{1}){\bigg ]}{\bigg [}x(n_{2})*h(n_{2}){\bigg ]}...{\bigg [}x(n_{M})*h(n_{M}){\bigg ]}}</annotation>

</semantics>

</math><img src="./bacab914a45991be9fa6c6a4cfc10fd4dcde7977.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.505ex; width:97.825ex; height:6.176ex;" alt="{\displaystyle x(n_{1},n_{2},...,n_{M})*{\overset {M}{\cdots }}*h(n_{1},n_{2},...,n_{M})={\bigg [}x(n_{1})*h(n_{1}){\bigg ]}{\bigg [}x(n_{2})*h(n_{2}){\bigg ]}...{\bigg [}x(n_{M})*h(n_{M}){\bigg ]}}" loading="lazy">

So, when the two signals are separable, the multidimensional convolution can be computed by computing <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n_{M}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n_{M}}</annotation>

</semantics>

</math><img src="./a6236d6e6a47dc7b2c51f17b4acdba49f7d9c022.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:3.354ex; height:2.009ex;" alt="{\displaystyle n_{M}}" loading="lazy"> one-dimensional convolutions.

<div class="mw-heading mw-heading3"><h3 id="Row-column_decomposition">Row-column decomposition</h3></div>

The row-column method can be applied when one of the signals in the convolution is separable. The method exploits the properties of separability in order to achieve a method of calculating the convolution of two multidimensional signals that is more computationally efficient than direct computation of each sample (given that one of the signals are separable).<a href="#cite_note-4">[4]</a> The following shows the mathematical reasoning behind the row-column decomposition approach (typically <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle h(n_{1},n_{2})}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle h(n_{1},n_{2})}</annotation>

</semantics>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mtd>

<mtd>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</munderover>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</munderover>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mtd>

</mtr>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</munderover>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</munderover>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mtd>

</mtr>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</munderover>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</munderover>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\begin{aligned}y(n_{1},n_{2})&=\sum _{k_{1}=-\infty }^{\infty }\sum _{k_{2}=-\infty }^{\infty }h(k_{1},k_{2})x(n_{1}-k_{1},n_{2}-k_{2})\\&=\sum _{k_{1}=-\infty }^{\infty }\sum _{k_{2}=-\infty }^{\infty }h_{1}(k_{1})h_{2}(k_{2})x(n_{1}-k_{1},n_{2}-k_{2})\\&=\sum _{k_{1}=-\infty }^{\infty }h_{1}(k_{1}){\Bigg [}\sum _{k_{2}=-\infty }^{\infty }h_{2}(k_{2})x(n_{1}-k_{1},n_{2}-k_{2}){\Bigg ]}\end{aligned}}}</annotation>

</semantics>

</math><img src="./86f1c70ca8840903d029d57545a0c6c9d2bfb93f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -10.671ex; width:60.613ex; height:22.509ex;" alt="{\displaystyle {\begin{aligned}y(n_{1},n_{2})&=\sum _{k_{1}=-\infty }^{\infty }\sum _{k_{2}=-\infty }^{\infty }h(k_{1},k_{2})x(n_{1}-k_{1},n_{2}-k_{2})\\&=\sum _{k_{1}=-\infty }^{\infty }\sum _{k_{2}=-\infty }^{\infty }h_{1}(k_{1})h_{2}(k_{2})x(n_{1}-k_{1},n_{2}-k_{2})\\&=\sum _{k_{1}=-\infty }^{\infty }h_{1}(k_{1}){\Bigg [}\sum _{k_{2}=-\infty }^{\infty }h_{2}(k_{2})x(n_{1}-k_{1},n_{2}-k_{2}){\Bigg ]}\end{aligned}}}" loading="lazy">

The value of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \sum _{k_{2}=-\infty }^{\infty }h_{2}(k_{2})x(n_{1}-k_{1},n_{2}-k_{2})}">

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</munderover>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \sum _{k_{2}=-\infty }^{\infty }h_{2}(k_{2})x(n_{1}-k_{1},n_{2}-k_{2})}</annotation>

</semantics>

</math><img src="./1cf0f8a12fe3bc264cfe1ddb15e1a9294730b43e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.338ex; width:32.026ex; height:7.176ex;" alt="{\displaystyle \sum _{k_{2}=-\infty }^{\infty }h_{2}(k_{2})x(n_{1}-k_{1},n_{2}-k_{2})}" loading="lazy"> can now be re-used when evaluating other <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle y}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y}</annotation>

</semantics>

</math><img src="./b8a6208ec717213d4317e666f1ae872e00620a0d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.155ex; height:2.009ex;" alt="{\displaystyle y}" loading="lazy"> values with a shared value of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n_{2}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n_{2}}</annotation>

</semantics>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mtd>

<mtd>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</munderover>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</munderover>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</mtd>

</mtr>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</munderover>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</munderover>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\begin{aligned}y(n_{1}+\delta ,n_{2})&=\sum _{k_{1}=-\infty }^{\infty }h_{1}(k_{1}){\Bigg [}\sum _{k_{2}=-\infty }^{\infty }h_{2}(k_{2})x(n_{1}-[k_{1}-\delta ],n_{2}-k_{2}){\Bigg ]}\\&=\sum _{k_{1}=-\infty }^{\infty }h_{1}(k_{1}+\delta ){\Bigg [}\sum _{k_{2}=-\infty }^{\infty }h_{2}(k_{2})x(n_{1}-k_{1},n_{2}-k_{2}){\Bigg ]}\end{aligned}}}</annotation>

</semantics>

</math><img src="./bac2dc2611f396121edc50328a4f3d5890e71236.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -7.171ex; width:69.685ex; height:15.509ex;" alt="{\displaystyle {\begin{aligned}y(n_{1}+\delta ,n_{2})&=\sum _{k_{1}=-\infty }^{\infty }h_{1}(k_{1}){\Bigg [}\sum _{k_{2}=-\infty }^{\infty }h_{2}(k_{2})x(n_{1}-[k_{1}-\delta ],n_{2}-k_{2}){\Bigg ]}\\&=\sum _{k_{1}=-\infty }^{\infty }h_{1}(k_{1}+\delta ){\Bigg [}\sum _{k_{2}=-\infty }^{\infty }h_{2}(k_{2})x(n_{1}-k_{1},n_{2}-k_{2}){\Bigg ]}\end{aligned}}}" loading="lazy">

Thus, the resulting convolution can be effectively calculated by first performing the convolution operation on all of the rows of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x(n_{1},n_{2})}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x(n_{1},n_{2})}</annotation>

</semantics>

A processor will load in the signal data needed for the given operation. For modern processors, data will be loaded from memory into the processors cache, which has faster access times than memory. The cache itself is partitioned into lines. When a cache line is loaded from memory, multiple data operands are loaded at once. Consider the optimized case where a row of signal data can fit entirely within the processor's cache. This particular processor would be able to access the data row-wise efficiently, but not column-wise since different data operands in the same column would lie on different cache lines.<a href="#cite_note-5">[5]</a> In order to take advantage of the way in which memory is accessed, it is more efficient to transpose the data set and then access it row-wise rather than attempt to access it column-wise. The algorithm then becomes:

<ol><li>Separate the separable two-dimensional signal <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle h(n_{1},n_{2})}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle h(n_{1},n_{2})}</annotation>

</semantics>

</math><img src="./3af74de774e14e28f2377ea93aa13ed591296300.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.08ex; height:2.843ex;" alt="{\displaystyle h(n_{1},n_{2})}" loading="lazy"> into two one-dimensional signals <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle h_{1}(n_{1})}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle h_{1}(n_{1})}</annotation>

</semantics>

</math><img src="./ae10808c76e94b3f5a92f96657149f811fc2febc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.651ex; height:2.843ex;" alt="{\displaystyle h_{1}(n_{1})}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle h_{2}(n_{2})}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle h_{2}(n_{2})}</annotation>

</semantics>

</math><img src="./30ad9af4173901bbb3804e7f5a2acff6498b1f3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.651ex; height:2.843ex;" alt="{\displaystyle h_{2}(n_{2})}" loading="lazy"></li>

<li>Perform row-wise convolution on the horizontal components of the signal <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x(n_{1},n_{2})}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x(n_{1},n_{2})}</annotation>

</semantics>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle h_{1}(n_{1})}</annotation>

</semantics>

</math><img src="./ae10808c76e94b3f5a92f96657149f811fc2febc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.651ex; height:2.843ex;" alt="{\displaystyle h_{1}(n_{1})}" loading="lazy"> to obtain <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle g(n_{1},n_{2})}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle g(n_{1},n_{2})}</annotation>

</semantics>

<li>Transpose the vertical components of the signal <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle g(n_{1},n_{2})}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle g(n_{1},n_{2})}</annotation>

</semantics>

<li>Perform row-wise convolution on the transposed vertical components of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle g(n_{1},n_{2})}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle g(n_{1},n_{2})}</annotation>

</semantics>

</math><img src="./fa8e45b7ad89eb84b134ab892ec2fad905b0bc16.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.857ex; height:2.843ex;" alt="{\displaystyle g(n_{1},n_{2})}" loading="lazy"> to get the desired output <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle y(n_{1},n_{2})}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y(n_{1},n_{2})}</annotation>

</semantics>

<div class="mw-heading mw-heading3"><h3 id="Computational_speedup_from_row-column_decomposition">Computational speedup from row-column decomposition</h3></div>

Examine the case where an image of size <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle X\times Y}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle X\times Y}</annotation>

</semantics>

</math><img src="./1613c1ff4b6fbfb6c80a8da83e90ad28f0ab3483.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:6.594ex; height:2.176ex;" alt="{\displaystyle X\times Y}" loading="lazy"> is being passed through a separable filter of size <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle J\times K}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle J\times K}</annotation>

</semantics>

</math><img src="./5cbd1a9234989a8bd3d3998e871e7d8a99cc7acb.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:6.378ex; height:2.176ex;" alt="{\displaystyle J\times K}" loading="lazy">. The image itself is not separable. If the result is calculated using the direct convolution approach without exploiting the separability of the filter, this will require approximately <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle XYJK}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle XYJK}</annotation>

</semantics>

</math><img src="./9fc76573b12bd4b6ae1b63fb584998afe9da4346.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:7.291ex; height:2.176ex;" alt="{\displaystyle XYJK}" loading="lazy"> multiplications and additions. If the separability of the filter is taken into account, the filtering can be performed in two steps. The first step will have <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle XYJ}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle XYJ}</annotation>

</semantics>

</math><img src="./c100ccac0fafac329122e4383cddf33906a30cfb.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.225ex; height:2.176ex;" alt="{\displaystyle XYJ}" loading="lazy"> multiplications and additions and the second step will have <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle XYK}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle XYK}</annotation>

</semantics>

</math><img src="./86a6aec6b4ae05200a6edfe44bdd9a5ef1406f3a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.819ex; height:2.176ex;" alt="{\displaystyle XYK}" loading="lazy">, resulting in a total of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle XYJ+XYK}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle XYJ+XYK}</annotation>

</semantics>

</math><img src="./8550b14d06e28a27aec3605d1af8329d25afc357.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:13.884ex; height:2.343ex;" alt="{\displaystyle XYJ+XYK}" loading="lazy"> or <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle XY(J+K)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle XY(J+K)}</annotation>

</semantics>

</math><img src="./b92ddcd08c2215f7ad581afce33ba579c06927a3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:11.94ex; height:2.843ex;" alt="{\displaystyle XY(J+K)}" loading="lazy"> multiplications and additions.<a href="#cite_note-6">[6]</a> A comparison of the computational complexity between direct and separable convolution is given in the following image:

<div class="mw-heading mw-heading2"><h2 id="Circular_convolution_of_discrete-valued_multidimensional_signals">Circular convolution of discrete-valued multidimensional signals</h2></div>

The premise behind the circular convolution approach on multidimensional signals is to develop a relation between the <a href="Convolution_theorem" title="Convolution theorem">Convolution theorem</a> and the <a href="Discrete_Fourier_transform" title="Discrete Fourier transform">Discrete Fourier transform</a> (DFT) that can be used to calculate the convolution between two finite-extent, discrete-valued signals.<a href="#cite_note-7">[7]</a>

<div class="mw-heading mw-heading3"><h3 id="Convolution_theorem_in_multiple_dimensions">Convolution theorem in multiple dimensions</h3></div>

For one-dimensional signals, the <a href="Convolution_theorem" title="Convolution theorem">Convolution Theorem</a> states that the <a href="Fourier_transform" title="Fourier transform">Fourier transform</a> of the convolution between two signals is equal to the product of the Fourier Transforms of those two signals. Thus, convolution in the time domain is equal to multiplication in the frequency domain. Mathematically, this principle is expressed via the following:<math display="block" xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle y(n)=h(n)*x(n)\longleftrightarrow Y(\omega )=H(\omega )X(\omega )}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y(n)=h(n)*x(n)\longleftrightarrow Y(\omega )=H(\omega )X(\omega )}</annotation>

</semantics>

</math>This principle is directly extendable to dealing with signals of multiple dimensions.<math display="block" xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle y(n_{1},n_{2},...,n_{M})=h(n_{1},n_{2},...,n_{M})*{\overset {M}{\cdots }}*x(n_{1},n_{2},...,n_{M})\longleftrightarrow Y(\omega _{1},\omega _{2},...,\omega _{M})=H(\omega _{1},\omega _{2},...,\omega _{M})X(\omega _{1},\omega _{2},...,\omega _{M})}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<mover>

</mover>

</mrow>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y(n_{1},n_{2},...,n_{M})=h(n_{1},n_{2},...,n_{M})*{\overset {M}{\cdots }}*x(n_{1},n_{2},...,n_{M})\longleftrightarrow Y(\omega _{1},\omega _{2},...,\omega _{M})=H(\omega _{1},\omega _{2},...,\omega _{M})X(\omega _{1},\omega _{2},...,\omega _{M})}</annotation>

</semantics>

</math> This property is readily extended to the usage with the <a href="Discrete_Fourier_transform" title="Discrete Fourier transform">Discrete Fourier transform</a> (DFT) as follows (note that linear convolution is replaced with circular convolution where <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \otimes }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \otimes }</annotation>

</semantics>

</math><img src="./de29098f5a34ee296a505681a0d5e875070f2aea.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:1.808ex; height:2.176ex;" alt="{\displaystyle \otimes }" loading="lazy"> is used to denote the circular convolution operation of size <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle N}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle N}</annotation>

</semantics>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y(n)=h(n)\otimes x(n)\longleftrightarrow Y(k)=H(k)X(k)}</annotation>

</semantics>

</math><img src="./433de02372999e5bd123444a5754286c75bc2b9c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:42.961ex; height:2.843ex;" alt="{\displaystyle y(n)=h(n)\otimes x(n)\longleftrightarrow Y(k)=H(k)X(k)}" loading="lazy">

When dealing with signals of multiple dimensions:<math display="block" xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle y(n_{1},n_{2},...,n_{M})=h(n_{1},n_{2},...,n_{M})\otimes {\overset {M}{\cdots }}\otimes x(n_{1},n_{2},...,n_{M})\longleftrightarrow Y(k_{1},k_{2},...,k_{M})=H(k_{1},k_{2},...,k_{M})X(k_{1},k_{2},...,k_{M})}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<mover>

</mover>

</mrow>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y(n_{1},n_{2},...,n_{M})=h(n_{1},n_{2},...,n_{M})\otimes {\overset {M}{\cdots }}\otimes x(n_{1},n_{2},...,n_{M})\longleftrightarrow Y(k_{1},k_{2},...,k_{M})=H(k_{1},k_{2},...,k_{M})X(k_{1},k_{2},...,k_{M})}</annotation>

</semantics>

</math>The circular convolutions here will be of size <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle N_{1},N_{2},...,N_{M}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle N_{1},N_{2},...,N_{M}}</annotation>

</semantics>

</math><img src="./b6c3240dd0750e5a7a74df35f8bbc51f12cd5307.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:15.87ex; height:2.509ex;" alt="{\displaystyle N_{1},N_{2},...,N_{M}}" loading="lazy">.

<div class="mw-heading mw-heading3"><h3 id="Circular_convolution_approach">Circular convolution approach</h3></div>

The motivation behind using the circular convolution approach is that it is based on the DFT. The premise behind circular convolution is to take the DFTs of the input signals, multiply them together, and then take the inverse DFT. Care must be taken such that a large enough DFT is used such that aliasing does not occur. The DFT is numerically computable when dealing with signals of finite-extent. One advantage this approach has is that since it requires taking the DFT and inverse DFT, it is possible to utilize efficient algorithms such as the <a href="Fast_Fourier_transform" title="Fast Fourier transform">Fast Fourier transform</a> (FFT). Circular convolution can also be computed in the time/spatial domain and not only in the frequency domain.

<div class="mw-heading mw-heading3"><h3 id="Choosing_DFT_size_to_avoid_aliasing">Choosing DFT size to avoid aliasing</h3></div>

Consider the following case where two finite-extent signals x and h are taken. For both signals, there is a corresponding DFT as follows:

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x(n_{1},n_{2})\longleftrightarrow X(k_{1},k_{2})}</annotation>

</semantics>

</math><img src="./2d08c8dab0139f71f40a48bcaf33c5b29e624ff5.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:24.034ex; height:2.843ex;" alt="{\displaystyle x(n_{1},n_{2})\longleftrightarrow X(k_{1},k_{2})}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle h(n_{1},n_{2})\longleftrightarrow H(k_{1},k_{2})}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle h(n_{1},n_{2})\longleftrightarrow H(k_{1},k_{2})}</annotation>

</semantics>

</math><img src="./34037daf0373ef9e3a8aca442c291fb4f16ff078.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:24.127ex; height:2.843ex;" alt="{\displaystyle h(n_{1},n_{2})\longleftrightarrow H(k_{1},k_{2})}" loading="lazy">

The region of support of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x(n_{1},n_{2})}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x(n_{1},n_{2})}</annotation>

</semantics>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 0\leq n_{1}\leq P_{1}-1}</annotation>

</semantics>

</math><img src="./41419684d78129fa7eef506f954564e3f88bae7a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:16.358ex; height:2.509ex;" alt="{\displaystyle 0\leq n_{1}\leq P_{1}-1}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 0\leq n_{2}\leq P_{2}-1}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 0\leq n_{2}\leq P_{2}-1}</annotation>

</semantics>

</math><img src="./52f3a15b3f4eb5797c33688560f6e32ef33a1ef9.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:16.358ex; height:2.509ex;" alt="{\displaystyle 0\leq n_{2}\leq P_{2}-1}" loading="lazy"> and the region of support of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle h(n_{1},n_{2})}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle h(n_{1},n_{2})}</annotation>

</semantics>

</math><img src="./3af74de774e14e28f2377ea93aa13ed591296300.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.08ex; height:2.843ex;" alt="{\displaystyle h(n_{1},n_{2})}" loading="lazy"> is <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 0\leq n_{1}\leq Q_{1}-1}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 0\leq n_{1}\leq Q_{1}-1}</annotation>

</semantics>

</math><img src="./af98d919c0e1a6be6e3300d902e8b1619fac35b8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:16.704ex; height:2.509ex;" alt="{\displaystyle 0\leq n_{1}\leq Q_{1}-1}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 0\leq n_{2}\leq Q_{2}-1}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 0\leq n_{2}\leq Q_{2}-1}</annotation>

</semantics>

</math><img src="./0db178f4da79374ca3846bbfecb1d40894ca5585.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:16.704ex; height:2.509ex;" alt="{\displaystyle 0\leq n_{2}\leq Q_{2}-1}" loading="lazy">.

The linear convolution of these two signals would be given as:<math display="block" xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle y_{linear}(n_{1},n_{2})=\sum _{m_{1}}\sum _{m_{2}}h(m_{1},m_{2})x(n_{1}-m_{1},n_{2}-m_{2})}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</munder>

<msub>

</mrow>

</msub>

</mrow>

</munder>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y_{linear}(n_{1},n_{2})=\sum _{m_{1}}\sum _{m_{2}}h(m_{1},m_{2})x(n_{1}-m_{1},n_{2}-m_{2})}</annotation>

</semantics>

</math>Given the regions of support of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x(n_{1},n_{2})}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x(n_{1},n_{2})}</annotation>

</semantics>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle h(n_{1},n_{2})}</annotation>

</semantics>

</math><img src="./3af74de774e14e28f2377ea93aa13ed591296300.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.08ex; height:2.843ex;" alt="{\displaystyle h(n_{1},n_{2})}" loading="lazy">, the region of support of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle y_{linear}(n_{1},n_{2})}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y_{linear}(n_{1},n_{2})}</annotation>

</semantics>

</math><img src="./803fcba42ba9181e925a2f8a27e2c3c1eb121301.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:13.534ex; height:2.843ex;" alt="{\displaystyle y_{linear}(n_{1},n_{2})}" loading="lazy"> will then be given as the following:

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 0\leq n_{1}\leq P_{1}+Q_{1}-1}</annotation>

</semantics>

</math><math display="block" xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 0\leq n_{2}\leq P_{2}+Q_{2}-1}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 0\leq n_{2}\leq P_{2}+Q_{2}-1}</annotation>

</semantics>

</math>Based on the regions of support of the two signals, a DFT of size <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle N_{1}\times N_{2}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle N_{1}\times N_{2}}</annotation>

</semantics>

</math><img src="./3c171fe7c7b4db533245217f2d0971824cd1ff13.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:8.681ex; height:2.509ex;" alt="{\displaystyle N_{1}\times N_{2}}" loading="lazy"> must be used where <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle N_{1}\geq \max(P_{1},Q_{1})}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle N_{1}\geq \max(P_{1},Q_{1})}</annotation>

</semantics>

</math><img src="./e5878fafb755b934018003ae14d874773debb4a7.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:18.627ex; height:2.843ex;" alt="{\displaystyle N_{1}\geq \max(P_{1},Q_{1})}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle N_{2}\geq \max(P_{2},Q_{2})}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle N_{2}\geq \max(P_{2},Q_{2})}</annotation>

</semantics>

</math><img src="./a9a881ef3973f1a6856c041b149c5fdcbf9b4a8a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:18.627ex; height:2.843ex;" alt="{\displaystyle N_{2}\geq \max(P_{2},Q_{2})}" loading="lazy"> since the same size DFT must be used on both signals. In the event where a DFT size larger than the extent of a signal is needed, the signal is zero-padded until it reaches the required length. After multiplying the DFTs and taking the inverse DFT on the result, the resulting circular convolution is then given by:

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</munder>

<msub>

</mrow>

</msub>

</mrow>

</munder>

</mrow>

<msub>

</mrow>

</msub>

</mrow>

<msub>

</mrow>

</msub>

</mrow>

</munderover>

<msub>

</mrow>

</msub>

</mrow>

<msub>

</mrow>

</msub>

</mrow>

</munderover>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y_{circular}(n_{1},n_{2})=\sum _{r_{1}}\sum _{r_{2}}{\Bigg [}\sum _{m_{1}=0}^{Q_{1}-1}\sum _{m_{2}=0}^{Q_{2}-1}h(m_{1},m_{2})x(n_{1}-m_{1}-r_{1}N_{1},n_{2}-m_{2}-r_{2}N_{2}){\Bigg ]}}</annotation>

</semantics>

</math><img src="./b357fcd547e161addd82bb52a99ec6a92ef013e4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.338ex; width:85.131ex; height:7.843ex;" alt="{\displaystyle y_{circular}(n_{1},n_{2})=\sum _{r_{1}}\sum _{r_{2}}{\Bigg [}\sum _{m_{1}=0}^{Q_{1}-1}\sum _{m_{2}=0}^{Q_{2}-1}h(m_{1},m_{2})x(n_{1}-m_{1}-r_{1}N_{1},n_{2}-m_{2}-r_{2}N_{2}){\Bigg ]}}" loading="lazy"> for <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (n_{1},n_{2})\in R_{N_{1}N_{2}}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (n_{1},n_{2})\in R_{N_{1}N_{2}}}</annotation>

</semantics>

</math><img src="./d38d2e653445834854271c9679101960b20d0201.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:16.88ex; height:3.009ex;" alt="{\displaystyle (n_{1},n_{2})\in R_{N_{1}N_{2}}}" loading="lazy">

<msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle R_{N_{1}N_{2}}\triangleq \{(n_{1},n_{2}):0\leq n_{1}\leq N_{1}-1,0\leq n_{2}\leq N_{2}-1\}}</annotation>

</semantics>

</math><img src="./7f005609b5a955fa206de2560bf3615f86245ef3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:55.897ex; height:3.176ex;" alt="{\displaystyle R_{N_{1}N_{2}}\triangleq \{(n_{1},n_{2}):0\leq n_{1}\leq N_{1}-1,0\leq n_{2}\leq N_{2}-1\}}" loading="lazy">

The result will be that <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle y_{circular}(n_{1},n_{2})}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y_{circular}(n_{1},n_{2})}</annotation>

</semantics>

</math><img src="./118e267b33795955331968bcc9683a7fd0351549.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:14.887ex; height:2.843ex;" alt="{\displaystyle y_{circular}(n_{1},n_{2})}" loading="lazy"> will be a spatially aliased version of the linear convolution result <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle y_{linear}(n_{1},n_{2})}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y_{linear}(n_{1},n_{2})}</annotation>

</semantics>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</munder>

<msub>

</mrow>

</msub>

</mrow>

</munder>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y_{circular}(n_{1},n_{2})=\sum _{r_{1}}\sum _{r_{2}}y_{linear}(n_{1}-r_{1}N_{1},n_{2}-r_{2}N_{2}){\mathrm {\,\,\,for\,\,\,} }(n_{1},n_{2})\in R_{N_{1}N_{2}}}</annotation>

</semantics>

</math><img src="./998d254fd38039ec17ad016d05cce104904aa73d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.171ex; width:76.873ex; height:5.676ex;" alt="{\displaystyle y_{circular}(n_{1},n_{2})=\sum _{r_{1}}\sum _{r_{2}}y_{linear}(n_{1}-r_{1}N_{1},n_{2}-r_{2}N_{2}){\mathrm {\,\,\,for\,\,\,} }(n_{1},n_{2})\in R_{N_{1}N_{2}}}" loading="lazy">

Then, in order to avoid aliasing between the spatially aliased replicas, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle N_{1}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle N_{1}}</annotation>

</semantics>

</math><img src="./71b670ae74954b8aacd4d720d9b2b2081f6d3869.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.92ex; height:2.509ex;" alt="{\displaystyle N_{1}}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle N_{2}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle N_{2}}</annotation>

</semantics>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle N_{1}\geq P_{1}+Q_{1}-1}</annotation>

</semantics>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle N_{2}\geq P_{2}+Q_{2}-1}</annotation>

</semantics>

</math><img src="./e7ba58b371262c83d8a9171bad071a383b06ae7a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:18.301ex; height:2.509ex;" alt="{\displaystyle N_{2}\geq P_{2}+Q_{2}-1}" loading="lazy">

If these conditions are satisfied, then the results of the circular convolution will equal that of the linear convolution (taking the main period of the circular convolution as the region of support). That is:

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y_{circular}(n_{1},n_{2})=y_{linear}(n_{1},n_{2})}</annotation>

</semantics>

</math><img src="./edb61ff3fef8bdc6d21bda8cbf1a8f9270742244.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:31.519ex; height:2.843ex;" alt="{\displaystyle y_{circular}(n_{1},n_{2})=y_{linear}(n_{1},n_{2})}" loading="lazy"> for <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (n_{1},n_{2})\in R_{N_{1}N_{2}}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (n_{1},n_{2})\in R_{N_{1}N_{2}}}</annotation>

</semantics>

<div class="mw-heading mw-heading3"><h3 id="Summary_of_procedure_using_DFTs">Summary of procedure using DFTs</h3></div>

The Convolution theorem and circular convolution can thus be used in the following manner to achieve a result that is equal to performing the linear convolution:<a href="#cite_note-8">[8]</a>

<ol><li>Choose <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle N_{1}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle N_{1}}</annotation>

</semantics>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle N_{2}}</annotation>

</semantics>

</math><img src="./597ea9dac049261fdda77c5176b050e6588d6bb9.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.92ex; height:2.509ex;" alt="{\displaystyle N_{2}}" loading="lazy"> to satisfy <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle N_{1}\geq P_{1}+Q_{1}-1}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle N_{1}\geq P_{1}+Q_{1}-1}</annotation>

</semantics>

</math><img src="./2139eccb20bab732886ea862d3ce13d2ef88c8ea.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:18.301ex; height:2.509ex;" alt="{\displaystyle N_{1}\geq P_{1}+Q_{1}-1}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle N_{2}\geq P_{2}+Q_{2}-1}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle N_{2}\geq P_{2}+Q_{2}-1}</annotation>

</semantics>

<li>Zero pad the signals <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle h(n_{1},n_{2})}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle h(n_{1},n_{2})}</annotation>

</semantics>

</math><img src="./3af74de774e14e28f2377ea93aa13ed591296300.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.08ex; height:2.843ex;" alt="{\displaystyle h(n_{1},n_{2})}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x(n_{1},n_{2})}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x(n_{1},n_{2})}</annotation>

</semantics>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle N_{1}\times N_{2}}</annotation>

</semantics>

<li>Compute the DFTs of both <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle h(n_{1},n_{2})}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle h(n_{1},n_{2})}</annotation>

</semantics>

</math><img src="./3af74de774e14e28f2377ea93aa13ed591296300.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.08ex; height:2.843ex;" alt="{\displaystyle h(n_{1},n_{2})}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x(n_{1},n_{2})}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x(n_{1},n_{2})}</annotation>

</semantics>

<li>Multiply the results of the DFTs to obtain <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle Y(k_{1},k_{2})=H(k_{1},k_{2})X(k_{1},k_{2})}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle Y(k_{1},k_{2})=H(k_{1},k_{2})X(k_{1},k_{2})}</annotation>

</semantics>

</math><img src="./6b9e9bf3b5ae468cf22f10f960a54dd8ae17a5bd.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:31.038ex; height:2.843ex;" alt="{\displaystyle Y(k_{1},k_{2})=H(k_{1},k_{2})X(k_{1},k_{2})}" loading="lazy"></li>

<li>The result of the IDFT of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle Y(k_{1},k_{2})}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle Y(k_{1},k_{2})}</annotation>

</semantics>

</math><img src="./8100043872d96d6c567a3df9175477fc8cdf6dc9.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.147ex; height:2.843ex;" alt="{\displaystyle Y(k_{1},k_{2})}" loading="lazy"> will then be equal to the result of performing linear convolution on the two signals</li></ol>

<div class="mw-heading mw-heading2"><h2 id="Overlap_and_add">Overlap and add</h2></div>

Another method to perform multidimensional convolution is the overlap and add approach. This method helps reduce the computational complexity often associated with multidimensional convolutions due to the vast amounts of data inherent in modern-day digital systems.<a href="#cite_note-9">[9]</a> For sake of brevity, the two-dimensional case is used as an example, but the same concepts can be extended to multiple dimensions.

Consider a two-dimensional convolution using a direct computation:

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</munderover>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</munderover>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y(n_{1},n_{2})=\sum _{k_{1}=-\infty }^{\infty }\sum _{k_{2}=-\infty }^{\infty }x(n_{1}-k_{1},n_{2}-k_{2})h(k_{1},k_{2})}</annotation>

</semantics>

</math><img src="./39383fd3ad4268f86c99a8fdaf7d4e6316dcc452.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.338ex; width:52.542ex; height:7.176ex;" alt="{\displaystyle y(n_{1},n_{2})=\sum _{k_{1}=-\infty }^{\infty }\sum _{k_{2}=-\infty }^{\infty }x(n_{1}-k_{1},n_{2}-k_{2})h(k_{1},k_{2})}" loading="lazy">

Assuming that the output signal <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle y(n_{1},n_{2})}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y(n_{1},n_{2})}</annotation>

</semantics>

</math><img src="./77e211279fccf49edf53dfb688b0dd59335cb24c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.897ex; height:2.843ex;" alt="{\displaystyle y(n_{1},n_{2})}" loading="lazy"> has N nonzero coefficients, and the impulse response has M nonzero samples, this direct computation would need MN multiplies and MN - 1 adds in order to compute. Using an FFT instead, the frequency response of the filter and the Fourier transform of the input would have to be stored in memory.<a href="#cite_note-10">[10]</a> Massive amounts of computations and excessive use of memory storage space pose a problematic issue as more dimensions are added. This is where the overlap and add convolution method comes in.

<div class="mw-heading mw-heading3"><h3 id="Decomposition_into_smaller_convolution_blocks">Decomposition into smaller convolution blocks</h3></div>

Instead of performing convolution on the blocks of information in their entirety, the information can be broken up into smaller blocks of dimensions <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle L_{1}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle L_{1}}</annotation>

</semantics>

</math><img src="./0e79dc1b001f8b923df475ed14de023cbc456013.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.637ex; height:2.509ex;" alt="{\displaystyle L_{1}}" loading="lazy">x<math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle L_{2}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle L_{2}}</annotation>

</semantics>

</math><img src="./c6a952cfe42c86b7741f55a817da0e251793a358.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.637ex; height:2.509ex;" alt="{\displaystyle L_{2}}" loading="lazy"> resulting in smaller FFTs, less computational complexity, and less storage needed. This can be expressed mathematically as follows:

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

<msub>

</mrow>

</msub>

</mrow>

</munderover>

</mrow>

<msub>

</mrow>

</msub>

</mrow>

</munderover>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x(n_{1},n_{2})=\sum _{i=1}^{P_{1}}\sum _{j=1}^{P_{2}}x_{ij}(n_{1},n_{2})}</annotation>

</semantics>

</math><img src="./4cb2c479074fe5165f1a1c27c3d1bc3955c08be9.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.338ex; width:30.201ex; height:7.676ex;" alt="{\displaystyle x(n_{1},n_{2})=\sum _{i=1}^{P_{1}}\sum _{j=1}^{P_{2}}x_{ij}(n_{1},n_{2})}" loading="lazy">

where <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x(n_{1},n_{2})}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x(n_{1},n_{2})}</annotation>

</semantics>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle N_{1}}</annotation>

</semantics>

</math><img src="./71b670ae74954b8aacd4d720d9b2b2081f6d3869.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.92ex; height:2.509ex;" alt="{\displaystyle N_{1}}" loading="lazy">x<math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle N_{2}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle N_{2}}</annotation>

</semantics>

</math><img src="./597ea9dac049261fdda77c5176b050e6588d6bb9.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.92ex; height:2.509ex;" alt="{\displaystyle N_{2}}" loading="lazy"> input signal, which is a summation of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P_{1}P_{2}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P_{1}P_{2}}</annotation>

</semantics>

</math><img src="./76d9794d001a7d37e056defea5cdc8c99055fc56.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:5.093ex; height:2.509ex;" alt="{\displaystyle P_{1}P_{2}}" loading="lazy"> block segments, with <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P_{1}=N_{1}/L_{1}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P_{1}=N_{1}/L_{1}}</annotation>

</semantics>

</math><img src="./8528229792f789d0dbe464753c7ffc556dea39f2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:12.365ex; height:2.843ex;" alt="{\displaystyle P_{1}=N_{1}/L_{1}}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P_{2}=N_{2}/L_{2}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P_{2}=N_{2}/L_{2}}</annotation>

</semantics>

</math><img src="./79314c3f78f90eb52288769e0c8a4f6990d57cad.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:12.365ex; height:2.843ex;" alt="{\displaystyle P_{2}=N_{2}/L_{2}}" loading="lazy">.

To produce the output signal, a two-dimensional convolution is performed:

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y(n_{1},n_{2})=x(n_{1},n_{2})**h(n_{1},n_{2})}</annotation>

</semantics>

</math><img src="./251c54b399251c077adbffd3453ce8c2f63dc904.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:33.503ex; height:2.843ex;" alt="{\displaystyle y(n_{1},n_{2})=x(n_{1},n_{2})**h(n_{1},n_{2})}" loading="lazy">

Substituting in for <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x(n_{1},n_{2})}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x(n_{1},n_{2})}</annotation>

</semantics>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

<msub>

</mrow>

</msub>

</mrow>

</munderover>

</mrow>

<msub>

</mrow>

</msub>

</mrow>

</munderover>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y(n_{1},n_{2})=\sum _{i=1}^{P_{1}}\sum _{j=1}^{P_{2}}x_{ij}(n_{1},n_{2})**h(n_{1},n_{2})}</annotation>

</semantics>

</math><img src="./0512ccbcef625f1cb2c78b077319b83453999622.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.338ex; width:42.465ex; height:7.676ex;" alt="{\displaystyle y(n_{1},n_{2})=\sum _{i=1}^{P_{1}}\sum _{j=1}^{P_{2}}x_{ij}(n_{1},n_{2})**h(n_{1},n_{2})}" loading="lazy">

This convolution adds more complexity than doing a direct convolution; however, since it is integrated with an FFT fast convolution, overlap-add performs faster and is a more memory-efficient method, making it practical for large sets of multidimensional data.

<div class="mw-heading mw-heading3"><h3 id="Breakdown_of_procedure">Breakdown of procedure</h3></div>

Let <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle h(n_{1},n_{2})}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle h(n_{1},n_{2})}</annotation>

</semantics>

</math><img src="./3af74de774e14e28f2377ea93aa13ed591296300.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.08ex; height:2.843ex;" alt="{\displaystyle h(n_{1},n_{2})}" loading="lazy"> be of size <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle M_{1}\times M_{2}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle M_{1}\times M_{2}}</annotation>

</semantics>

</math><img src="./1af0125b910172f776ce60bc9c76ac61991e644b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:9.457ex; height:2.509ex;" alt="{\displaystyle M_{1}\times M_{2}}" loading="lazy">:

<ol><li>Break input <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x(n_{1},n_{2})}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x(n_{1},n_{2})}</annotation>

</semantics>

</math><img src="./85ed8c47c0c37801b032df0db40fa6de35109737.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.071ex; height:2.843ex;" alt="{\displaystyle x(n_{1},n_{2})}" loading="lazy"> into non-overlapping blocks of dimensions <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle L_{1}\times L_{2}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle L_{1}\times L_{2}}</annotation>

</semantics>

</math><img src="./8bc7c5d93f88695ca2e0ab6fa6c6faf448b55c0f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:8.115ex; height:2.509ex;" alt="{\displaystyle L_{1}\times L_{2}}" loading="lazy">.</li>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle h(n_{1},n_{2})}</annotation>

</semantics>

</math><img src="./3af74de774e14e28f2377ea93aa13ed591296300.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.08ex; height:2.843ex;" alt="{\displaystyle h(n_{1},n_{2})}" loading="lazy"> such that it has dimensions (<math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle L_{1}+M_{1}-1}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle L_{1}+M_{1}-1}</annotation>

</semantics>

</math><img src="./f829b1fe2dff75b375f799cc44bcc1aa4698041d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:12.789ex; height:2.509ex;" alt="{\displaystyle L_{1}+M_{1}-1}" loading="lazy">) <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \times }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \times }</annotation>

</semantics>

</math><img src="./0ffafff1ad26cbe49045f19a67ce532116a32703.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: 0.019ex; margin-bottom: -0.19ex; width:1.808ex; height:1.509ex;" alt="{\displaystyle \times }" loading="lazy"> (<math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle L_{2}+M_{2}-1}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle L_{2}+M_{2}-1}</annotation>

</semantics>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle H(k_{1},k_{2})}</annotation>

</semantics>

</math><img src="./9c5a9f83aec94070c1529bc1a91affda6455acf8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.438ex; height:2.843ex;" alt="{\displaystyle H(k_{1},k_{2})}" loading="lazy">.</li>

<li>For each input block:

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x_{ij}(n_{1},n_{2})}</annotation>

</semantics>

</math><img src="./a2f234d35fa37b84d5336ed6e5cd877b84d4eb69.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:10.548ex; height:3.009ex;" alt="{\displaystyle x_{ij}(n_{1},n_{2})}" loading="lazy"> to be of dimensions (<math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle L_{1}+M_{1}-1}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle L_{1}+M_{1}-1}</annotation>

</semantics>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \times }</annotation>

</semantics>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle L_{2}+M_{2}-1}</annotation>

</semantics>

<li>Take discrete Fourier transform of each block to give <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle X_{ij}(k_{1},k_{2})}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle X_{ij}(k_{1},k_{2})}</annotation>

</semantics>

</math><img src="./023e0a02ddd456ba0251fe4f614eb8afacc3523c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:10.776ex; height:3.009ex;" alt="{\displaystyle X_{ij}(k_{1},k_{2})}" loading="lazy">.</li>

<li>Multiply to get <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle Y_{ij}(k_{1},k_{2})=X_{ij}(k_{1},k_{2})H(k_{1},k_{2})}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle Y_{ij}(k_{1},k_{2})=X_{ij}(k_{1},k_{2})H(k_{1},k_{2})}</annotation>

</semantics>

</math><img src="./599f42ea1851a03c93843b6c3769b3ca9ff409f2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:33.514ex; height:3.009ex;" alt="{\displaystyle Y_{ij}(k_{1},k_{2})=X_{ij}(k_{1},k_{2})H(k_{1},k_{2})}" loading="lazy">.</li>

<li>Take inverse discrete Fourier transform of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle Y_{ij}(k_{1},k_{2})}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle Y_{ij}(k_{1},k_{2})}</annotation>

</semantics>

</math><img src="./40e5574617a00df4fa9567d13768730475ca37cf.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:10.202ex; height:3.009ex;" alt="{\displaystyle Y_{ij}(k_{1},k_{2})}" loading="lazy"> to get <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle y_{ij}(n_{1},n_{2})}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y_{ij}(n_{1},n_{2})}</annotation>

</semantics>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y(n_{1},n_{2})}</annotation>

</semantics>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (M_{1}-1)}</annotation>

</semantics>

</math><img src="./a2d1384a191be99314ac14f7d3272d64a6b181f3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.12ex; height:2.843ex;" alt="{\displaystyle (M_{1}-1)}" loading="lazy"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \times }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \times }</annotation>

</semantics>

</math><img src="./0ffafff1ad26cbe49045f19a67ce532116a32703.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: 0.019ex; margin-bottom: -0.19ex; width:1.808ex; height:1.509ex;" alt="{\displaystyle \times }" loading="lazy"> <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (M_{2}-1)}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (M_{2}-1)}</annotation>

</semantics>

</math><img src="./3a6c25a6f729ff7cb2ea02e38f9f65dfadd482da.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.12ex; height:2.843ex;" alt="{\displaystyle (M_{2}-1)}" loading="lazy"> samples of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle y_{ij}(n_{1},n_{2})}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y_{ij}(n_{1},n_{2})}</annotation>

</semantics>

</math><img src="./9d13ae9ab608d0acd4da891013fdde27c2047b05.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:10.358ex; height:3.009ex;" alt="{\displaystyle y_{ij}(n_{1},n_{2})}" loading="lazy"> with the first <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (M_{1}-1)}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (M_{1}-1)}</annotation>

</semantics>

</math><img src="./a2d1384a191be99314ac14f7d3272d64a6b181f3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.12ex; height:2.843ex;" alt="{\displaystyle (M_{1}-1)}" loading="lazy"> <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \times }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \times }</annotation>

</semantics>

</math><img src="./0ffafff1ad26cbe49045f19a67ce532116a32703.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: 0.019ex; margin-bottom: -0.19ex; width:1.808ex; height:1.509ex;" alt="{\displaystyle \times }" loading="lazy"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (M_{2}-1)}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (M_{2}-1)}</annotation>

</semantics>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y_{i+1,j+1}(n_{1},n_{2})}</annotation>

</semantics>

</math><img src="./d05931e86fbfab54f318ed03fbf9309283a5f95e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:15.016ex; height:3.009ex;" alt="{\displaystyle y_{i+1,j+1}(n_{1},n_{2})}" loading="lazy"> to get the result.<a href="#cite_note-:3-11">[11]</a></li></ol>

<div class="mw-heading mw-heading3"><h3 id="Pictorial_method_of_operation">Pictorial method of operation</h3></div>

In order to visualize the overlap-add method more clearly, the following illustrations examine the method graphically. Assume that the input <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x(n_{1},n_{2})}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x(n_{1},n_{2})}</annotation>

</semantics>

</math><img src="./85ed8c47c0c37801b032df0db40fa6de35109737.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.071ex; height:2.843ex;" alt="{\displaystyle x(n_{1},n_{2})}" loading="lazy"> has a square region support of length N in both vertical and horizontal directions as shown in the figure below. It is then broken up into four smaller segments in such a way that it is now composed of four smaller squares. Each block of the aggregate signal has dimensions <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (N/2)}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (N/2)}</annotation>

</semantics>

</math><img src="./9818fbbf6cc8f400815e2421b58679ec3d03c73d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.198ex; height:2.843ex;" alt="{\displaystyle (N/2)}" loading="lazy"> <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \times }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \times }</annotation>

</semantics>

</math><img src="./0ffafff1ad26cbe49045f19a67ce532116a32703.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: 0.019ex; margin-bottom: -0.19ex; width:1.808ex; height:1.509ex;" alt="{\displaystyle \times }" loading="lazy"> <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (N/2)}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (N/2)}</annotation>

</semantics>

</math><img src="./9818fbbf6cc8f400815e2421b58679ec3d03c73d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.198ex; height:2.843ex;" alt="{\displaystyle (N/2)}" loading="lazy">. Then, each component is convolved with the impulse response of the filter. Note that an advantage for an implementation such as this can be visualized here since each of these convolutions can be parallelized on a computer, as long as the computer has sufficient memory and resources to store and compute simultaneously.

In the figure below, the first graph on the left represents the convolution corresponding to the component of the input <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x_{0,0}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x_{0,0}}</annotation>

</semantics>

</math><img src="./86ab3beb3b666d1a21786e8e4048fbda5d5c7a73.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:3.663ex; height:2.343ex;" alt="{\displaystyle x_{0,0}}" loading="lazy"> with the corresponding impulse response <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle h(n_{1},n_{2})}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle h(n_{1},n_{2})}</annotation>

</semantics>

</math><img src="./3af74de774e14e28f2377ea93aa13ed591296300.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.08ex; height:2.843ex;" alt="{\displaystyle h(n_{1},n_{2})}" loading="lazy">. To the right of that, the input <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x_{1,0}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x_{1,0}}</annotation>

</semantics>

</math><img src="./7a2a27b8eee5d0707204e7f679e06e6af293ab0a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:3.663ex; height:2.343ex;" alt="{\displaystyle x_{1,0}}" loading="lazy"> is then convolved with the impulse response <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle h(n_{1},n_{2})}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle h(n_{1},n_{2})}</annotation>

</semantics>

The same process is done for the other two inputs respectively, and they are accumulated together in order to form the convolution. This is depicted to the left.

Assume that the filter impulse response <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle h(n_{1},n_{2})}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle h(n_{1},n_{2})}</annotation>

</semantics>

</math><img src="./3af74de774e14e28f2377ea93aa13ed591296300.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.08ex; height:2.843ex;" alt="{\displaystyle h(n_{1},n_{2})}" loading="lazy"> has a region of support of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (N/8)}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (N/8)}</annotation>

</semantics>

</math><img src="./5ae675de43d0cb8fa0e29925ba919287117c9dab.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.198ex; height:2.843ex;" alt="{\displaystyle (N/8)}" loading="lazy"> in both dimensions. This entails that each convolution convolves signals with dimensions <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (N/2)}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (N/2)}</annotation>

</semantics>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \times }</annotation>

</semantics>

</math><img src="./0ffafff1ad26cbe49045f19a67ce532116a32703.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: 0.019ex; margin-bottom: -0.19ex; width:1.808ex; height:1.509ex;" alt="{\displaystyle \times }" loading="lazy"> <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (N/8)}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (N/8)}</annotation>

</semantics>

</math><img src="./5ae675de43d0cb8fa0e29925ba919287117c9dab.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.198ex; height:2.843ex;" alt="{\displaystyle (N/8)}" loading="lazy"> in both <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n_{1}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n_{1}}</annotation>

</semantics>

</math><img src="./ee784b70e772f55ede5e6e0bdc929994bff63413.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.449ex; height:2.009ex;" alt="{\displaystyle n_{1}}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n_{2}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n_{2}}</annotation>

</semantics>

</math><img src="./840e456e3058bc0be28e5cf653b170cdbfcc3be4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.449ex; height:2.009ex;" alt="{\displaystyle n_{2}}" loading="lazy"> directions, which leads to overlap (highlighted in blue) since the length of each individual convolution is equivalent to:

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (N/2)}</annotation>

</semantics>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle +}</annotation>

</semantics>

</math><img src="./fe6ef363cd19902d1a7a71fb1c8b21e8ede52406.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:1.808ex; height:2.176ex;" alt="{\displaystyle +}" loading="lazy"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (N/8)}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (N/8)}</annotation>

</semantics>

</math><img src="./5ae675de43d0cb8fa0e29925ba919287117c9dab.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.198ex; height:2.843ex;" alt="{\displaystyle (N/8)}" loading="lazy"> <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle -}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle -}</annotation>

</semantics>

</math><img src="./04bd52ce670743d3b61bec928a7ec9f47309eb36.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:1.808ex; height:2.176ex;" alt="{\displaystyle -}" loading="lazy"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 1}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 1}</annotation>

</semantics>

</math><img src="./92d98b82a3778f043108d4e20960a9193df57cbf.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.162ex; height:2.176ex;" alt="{\displaystyle 1}" loading="lazy"> = <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (5/8)N-1}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (5/8)N-1}</annotation>

</semantics>

</math><img src="./1e1ce5e3a4e0dd96093ed28d2ba6581856bb1bca.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:11.363ex; height:2.843ex;" alt="{\displaystyle (5/8)N-1}" loading="lazy">

in both directions. The lighter blue portion correlates to the overlap between two adjacent convolutions, whereas the darker blue portion correlates to overlap between all four convolutions. All of these overlap portions are added together in addition to the convolutions in order to form the combined convolution <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle y(n_{1},n_{2})}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y(n_{1},n_{2})}</annotation>

</semantics>

<div class="mw-heading mw-heading2"><h2 id="Overlap_and_save">Overlap and save</h2></div>

The overlap and save method, just like the overlap and add method, is also used to reduce the computational complexity associated with discrete-time convolutions. This method, coupled with the FFT, allows for massive amounts of data to be filtered through a digital system while minimizing the necessary memory space used for computations on massive arrays of data.

<div class="mw-heading mw-heading3"><h3 id="Comparison_to_overlap_and_add">Comparison to overlap and add</h3></div>

The overlap and save method is very similar to the overlap and add methods with a few notable exceptions. The overlap-add method involves a linear convolution of discrete-time signals, whereas the overlap-save method involves the principle of circular convolution. In addition, the overlap and save method only uses a one-time zero padding of the impulse response, while the overlap-add method involves a zero-padding for every convolution on each input component. Instead of using zero padding to prevent time-domain aliasing like its overlap-add counterpart, overlap-save simply discards all points of aliasing, and saves the previous data in one block to be copied into the convolution for the next block.

In one dimension, the performance and storage metric differences between the two methods is minimal. However, in the multidimensional convolution case, the overlap-save method is preferred over the overlap-add method in terms of speed and storage abilities.<a href="#cite_note-13">[13]</a> Just as in the overlap and add case, the procedure invokes the two-dimensional case but can easily be extended to all multidimensional procedures.

<div class="mw-heading mw-heading3"><h3 id="Breakdown_of_procedure_2">Breakdown of procedure</h3></div>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle h(n_{1},n_{2})}</annotation>

</semantics>

</math><img src="./3af74de774e14e28f2377ea93aa13ed591296300.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.08ex; height:2.843ex;" alt="{\displaystyle h(n_{1},n_{2})}" loading="lazy"> be of size <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle M_{1}\times M_{2}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle M_{1}\times M_{2}}</annotation>

</semantics>

<ol><li>Insert <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (M_{1}-1)}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (M_{1}-1)}</annotation>

</semantics>

</math><img src="./a2d1384a191be99314ac14f7d3272d64a6b181f3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.12ex; height:2.843ex;" alt="{\displaystyle (M_{1}-1)}" loading="lazy"> columns and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (M_{2}-1)}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (M_{2}-1)}</annotation>

</semantics>

</math><img src="./3a6c25a6f729ff7cb2ea02e38f9f65dfadd482da.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.12ex; height:2.843ex;" alt="{\displaystyle (M_{2}-1)}" loading="lazy"> rows of zeroes at the beginning of the input signal <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x(n_{1},n_{2})}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x(n_{1},n_{2})}</annotation>

</semantics>

<li>Split the corresponding signal into overlapping segments of dimensions (<math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle L_{1}+M_{1}-1}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle L_{1}+M_{1}-1}</annotation>

</semantics>

</math><img src="./f829b1fe2dff75b375f799cc44bcc1aa4698041d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:12.789ex; height:2.509ex;" alt="{\displaystyle L_{1}+M_{1}-1}" loading="lazy">)<math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \times }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \times }</annotation>

</semantics>

</math><img src="./0ffafff1ad26cbe49045f19a67ce532116a32703.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: 0.019ex; margin-bottom: -0.19ex; width:1.808ex; height:1.509ex;" alt="{\displaystyle \times }" loading="lazy">(<math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle L_{2}+M_{2}-1}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle L_{2}+M_{2}-1}</annotation>

</semantics>

</math><img src="./97597f452fe2091b679e353c5b0eca858818dbed.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:12.789ex; height:2.509ex;" alt="{\displaystyle L_{2}+M_{2}-1}" loading="lazy">) in which each two-dimensional block will overlap by <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (M_{1}-1)}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (M_{1}-1)}</annotation>

</semantics>

</math><img src="./a2d1384a191be99314ac14f7d3272d64a6b181f3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.12ex; height:2.843ex;" alt="{\displaystyle (M_{1}-1)}" loading="lazy"> <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \times }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \times }</annotation>

</semantics>

</math><img src="./0ffafff1ad26cbe49045f19a67ce532116a32703.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: 0.019ex; margin-bottom: -0.19ex; width:1.808ex; height:1.509ex;" alt="{\displaystyle \times }" loading="lazy"> <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (M_{2}-1)}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (M_{2}-1)}</annotation>

</semantics>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle h(n_{1},n_{2})}</annotation>

</semantics>

</math><img src="./3af74de774e14e28f2377ea93aa13ed591296300.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.08ex; height:2.843ex;" alt="{\displaystyle h(n_{1},n_{2})}" loading="lazy"> such that it has dimensions (<math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle L_{1}+M_{1}-1}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle L_{1}+M_{1}-1}</annotation>

</semantics>

</math><img src="./f829b1fe2dff75b375f799cc44bcc1aa4698041d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:12.789ex; height:2.509ex;" alt="{\displaystyle L_{1}+M_{1}-1}" loading="lazy">)<math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \times }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \times }</annotation>

</semantics>

</math><img src="./0ffafff1ad26cbe49045f19a67ce532116a32703.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: 0.019ex; margin-bottom: -0.19ex; width:1.808ex; height:1.509ex;" alt="{\displaystyle \times }" loading="lazy">(<math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle L_{2}+M_{2}-1}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle L_{2}+M_{2}-1}</annotation>

</semantics>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle H(k_{1},k_{2})}</annotation>

</semantics>

<li>For each input block:

<ol><li>Take discrete Fourier transform of each block to give <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle X_{ij}(k_{1},k_{2})}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle X_{ij}(k_{1},k_{2})}</annotation>

</semantics>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle Y_{ij}(k_{1},k_{2})=X_{ij}(k_{1},k_{2})H(k_{1},k_{2})}</annotation>

</semantics>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle Y_{ij}(k_{1},k_{2})}</annotation>

</semantics>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y_{ij}(n_{1},n_{2})}</annotation>

</semantics>

<li>Get rid of the first <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (M_{1}-1)}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (M_{1}-1)}</annotation>

</semantics>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \times }</annotation>

</semantics>

</math><img src="./0ffafff1ad26cbe49045f19a67ce532116a32703.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: 0.019ex; margin-bottom: -0.19ex; width:1.808ex; height:1.509ex;" alt="{\displaystyle \times }" loading="lazy"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (M_{2}-1)}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (M_{2}-1)}</annotation>

</semantics>

</math><img src="./3a6c25a6f729ff7cb2ea02e38f9f65dfadd482da.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.12ex; height:2.843ex;" alt="{\displaystyle (M_{2}-1)}" loading="lazy"> for each output block <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle y_{ij}(n_{1},n_{2})}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y_{ij}(n_{1},n_{2})}</annotation>

</semantics>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y(n_{1},n_{2})}</annotation>

</semantics>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (L_{1}\times L_{2})}</annotation>

</semantics>

</math><img src="./2f94cc2098ca819ab2bd7524e3b429387e5b8d1d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.924ex; height:2.843ex;" alt="{\displaystyle (L_{1}\times L_{2})}" loading="lazy"> samples for each output block <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle y_{ij}(n_{1},n_{2})}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y_{ij}(n_{1},n_{2})}</annotation>

</semantics>

</math><img src="./9d13ae9ab608d0acd4da891013fdde27c2047b05.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:10.358ex; height:3.009ex;" alt="{\displaystyle y_{ij}(n_{1},n_{2})}" loading="lazy">.<a href="#cite_note-:3-11">[11]</a></li></ol>

<div class="mw-heading mw-heading2"><h2 id="The_helix_transform">The helix transform</h2></div>

Similar to row-column decomposition, the helix transform computes the multidimensional convolution by incorporating one-dimensional convolutional properties and operators. Instead of using the separability of signals, however, it maps the Cartesian coordinate space to a helical coordinate space allowing for a mapping from a multidimensional space to a one-dimensional space.

<div class="mw-heading mw-heading3"><h3 id="Multidimensional_convolution_with_one-dimensional_convolution_methods">Multidimensional convolution with one-dimensional convolution methods</h3></div>

To understand the helix transform, it is useful to first understand how a multidimensional convolution can be broken down into a one-dimensional convolution. Assume that the two signals to be convolved are <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle X_{M\times N}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle X_{M\times N}}</annotation>

</semantics>

</math><img src="./a18d2e6634c33987c75b631e0a026050e42c35ea.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:6.621ex; height:2.509ex;" alt="{\displaystyle X_{M\times N}}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle Y_{K\times L}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle Y_{K\times L}}</annotation>

</semantics>

</math><img src="./9daf47f50d0ee7e6205f3eb41073fb009b317360.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:5.441ex; height:2.509ex;" alt="{\displaystyle Y_{K\times L}}" loading="lazy">, which results in an output <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle Z_{(M-K+1)\times (N-L+1)}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle Z_{(M-K+1)\times (N-L+1)}}</annotation>

</semantics>

</math><img src="./4c4dff472523ecaed1d99eae013eb51200ef4403.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.171ex; width:18.181ex; height:3.009ex;" alt="{\displaystyle Z_{(M-K+1)\times (N-L+1)}}" loading="lazy">. This is expressed as follows:

</mrow>

</mrow>

</munderover>

</mrow>

</mrow>

</munderover>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle Z(i,j)=\sum _{m=0}^{M-1}\sum _{n=0}^{N-1}X(m,n)Y(i-m,j-n)}</annotation>

</semantics>

</math><img src="./c9236cadbd3f3c685e641e979dc878c9bc147d41.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.005ex; width:41.295ex; height:7.343ex;" alt="{\displaystyle Z(i,j)=\sum _{m=0}^{M-1}\sum _{n=0}^{N-1}X(m,n)Y(i-m,j-n)}" loading="lazy">

Next, two matrices are created that zero pad each input in both dimensions such that each input has equivalent dimensions, i.e.

<msup>

</msup>

</mrow>

<mrow>

<mtr>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbf {X'} ={\begin{bmatrix}X&0\\0&0\\\end{bmatrix}}}</annotation>

</semantics>

</math><img src="./edb11f074fa68c98754da2d16474ecc30dd0932b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.505ex; width:14.474ex; height:6.176ex;" alt="{\displaystyle \mathbf {X'} ={\begin{bmatrix}X&0\\0&0\\\end{bmatrix}}}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbf {Y'} ={\begin{bmatrix}Y&0\\0&0\\\end{bmatrix}}}">

<msup>

</msup>

</mrow>

<mrow>

<mtr>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbf {Y'} ={\begin{bmatrix}Y&0\\0&0\\\end{bmatrix}}}</annotation>

</semantics>

</math><img src="./299b6c87d4b26357f0185af743c025427a4456ad.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.505ex; width:14.267ex; height:6.176ex;" alt="{\displaystyle \mathbf {Y'} ={\begin{bmatrix}Y&0\\0&0\\\end{bmatrix}}}" loading="lazy">

where each of the input matrices are now of dimensions <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (M+K-1)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (M+K-1)}</annotation>

</semantics>

</math><img src="./6c9a115c21b97f621db7a1ff1fa6ddc9350b9dea.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:13.161ex; height:2.843ex;" alt="{\displaystyle (M+K-1)}" loading="lazy"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \times }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \times }</annotation>

</semantics>

</math><img src="./0ffafff1ad26cbe49045f19a67ce532116a32703.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: 0.019ex; margin-bottom: -0.19ex; width:1.808ex; height:1.509ex;" alt="{\displaystyle \times }" loading="lazy"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (N+L-1)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (N+L-1)}</annotation>

</semantics>

</math><img src="./c22b1c652d0c9915f1663d077df92385bcbadd04.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:12.299ex; height:2.843ex;" alt="{\displaystyle (N+L-1)}" loading="lazy">. It is then possible to implement column-wise lexicographic ordering in order to convert the modified matrices into vectors, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle X''}">

<msup>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle X''}</annotation>

</semantics>

</math><img src="./67b827334f818c61a8b86e5d1ea9a3203c8e074b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:3.134ex; height:2.509ex;" alt="{\displaystyle X''}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle Y''}">

<msup>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle Y''}</annotation>

</semantics>

</math><img src="./0e3d2e9a4ff5f48169a01db9117bb418865177a9.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.171ex; width:3.037ex; height:2.343ex;" alt="{\displaystyle Y''}" loading="lazy">. In order to minimize the number of unimportant samples in each vector, each vector is truncated after the last sample in the original matrices <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle X}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle X}</annotation>

</semantics>

</math><img src="./68baa052181f707c662844a465bfeeb135e82bab.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.98ex; height:2.176ex;" alt="{\displaystyle X}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle Y}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle Y}</annotation>

</semantics>

</math><img src="./961d67d6b454b4df2301ac571808a3538b3a6d3f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.171ex; width:1.773ex; height:2.009ex;" alt="{\displaystyle Y}" loading="lazy"> respectively. Given this, the length of vector <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle X''}">

<msup>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle X''}</annotation>

</semantics>

<msup>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle Y''}</annotation>

</semantics>

<msub>

<msup>

</msup>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle l_{X''}=}</annotation>

</semantics>

</math><img src="./06617f3d52f0402f1c84a2560a665c4e9bdd90da.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.69ex; height:2.676ex;" alt="{\displaystyle l_{X''}=}" loading="lazy"> <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (M+K-1)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (M+K-1)}</annotation>

</semantics>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \times }</annotation>

</semantics>

</math><img src="./0ffafff1ad26cbe49045f19a67ce532116a32703.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: 0.019ex; margin-bottom: -0.19ex; width:1.808ex; height:1.509ex;" alt="{\displaystyle \times }" loading="lazy"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (N-1)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (N-1)}</annotation>

</semantics>

</math><img src="./cb0cf1c006bf96c188ea21e52c3a286661dba198.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.876ex; height:2.843ex;" alt="{\displaystyle (N-1)}" loading="lazy"> + <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle M}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle M}</annotation>

</semantics>

</math><img src="./f82cade9898ced02fdd08712e5f0c0151758a0dd.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.442ex; height:2.176ex;" alt="{\displaystyle M}" loading="lazy">

<msub>

<msup>

</msup>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle l_{Y''}=}</annotation>

</semantics>

</math><img src="./b9133e1814d69e42ee4d241db347134edf65cbf4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.621ex; height:2.676ex;" alt="{\displaystyle l_{Y''}=}" loading="lazy"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (M+K-1)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (M+K-1)}</annotation>

</semantics>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \times }</annotation>

</semantics>

</math><img src="./0ffafff1ad26cbe49045f19a67ce532116a32703.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: 0.019ex; margin-bottom: -0.19ex; width:1.808ex; height:1.509ex;" alt="{\displaystyle \times }" loading="lazy"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (L-1)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (L-1)}</annotation>

</semantics>

</math><img src="./83b681d611d057fd92e0f72e8bbd4403dcd8eb95.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.395ex; height:2.843ex;" alt="{\displaystyle (L-1)}" loading="lazy"> + <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle K}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle K}</annotation>

</semantics>

</math><img src="./2b76fce82a62ed5461908f0dc8f037de4e3686b0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.066ex; height:2.176ex;" alt="{\displaystyle K}" loading="lazy">

The length of the convolution of these two vectors, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle Z''}">

<msup>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle Z''}</annotation>

</semantics>

<msub>

<msup>

</msup>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle l_{Z''}=}</annotation>

</semantics>

</math><img src="./df4f9ffae990cc04370ec4cb3141b545702d01c6.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.486ex; height:2.676ex;" alt="{\displaystyle l_{Z''}=}" loading="lazy"> <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle l_{Y''}+}">

<msub>

<msup>

</msup>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle l_{Y''}+}</annotation>

</semantics>

</math><img src="./109c297fb4fa5878f77f2217c60e44f2b57032e1.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.976ex; height:2.676ex;" alt="{\displaystyle l_{Y''}+}" loading="lazy"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle l_{X''}}">

<msub>

<msup>

</msup>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle l_{X''}}</annotation>

</semantics>

</math><img src="./4d10b3396f648a750817babb153dac1e2286af7d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:3.236ex; height:2.676ex;" alt="{\displaystyle l_{X''}}" loading="lazy"> <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle =(M+K-1)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle =(M+K-1)}</annotation>

</semantics>

</math><img src="./397e6682b62824aaeb8d64066356c31feb0ffe3e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:15.614ex; height:2.843ex;" alt="{\displaystyle =(M+K-1)}" loading="lazy"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \times }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \times }</annotation>

</semantics>

</math><img src="./0ffafff1ad26cbe49045f19a67ce532116a32703.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: 0.019ex; margin-bottom: -0.19ex; width:1.808ex; height:1.509ex;" alt="{\displaystyle \times }" loading="lazy"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (N+L-1)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (N+L-1)}</annotation>

</semantics>

This vector length is equivalent to the dimensions of the original matrix output <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle Z}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle Z}</annotation>

</semantics>

</math><img src="./1cc6b75e09a8aa3f04d8584b11db534f88fb56bd.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.68ex; height:2.176ex;" alt="{\displaystyle Z}" loading="lazy">, making converting back to a matrix a direct transformation. Thus, the vector, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle Z''}">

<msup>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle Z''}</annotation>

</semantics>

</math><img src="./07e8aa693bfc0f7c74f19f5c1934808f88ec97e0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.846ex; height:2.509ex;" alt="{\displaystyle Z''}" loading="lazy">, is converted back to matrix form, which produces the output of the two-dimensional discrete convolution.<a href="#cite_note-:1-14">[14]</a>

<div class="mw-heading mw-heading3"><h3 id="Filtering_on_a_helix">Filtering on a helix</h3></div>

When working on a two-dimensional Cartesian mesh, a Fourier transform along either axes will result in the two-dimensional plane becoming a cylinder as the end of each column or row attaches to its respective top forming a cylinder. Filtering on a helix behaves in a similar fashion, except in this case, the bottom of each column attaches to the top of the next column, resulting in a helical mesh. This is illustrated below. The darkened tiles represent the filter coefficients.

If this helical structure is then sliced and unwound into a one-dimensional strip, the same filter coefficients on the 2-d Cartesian plane will match up with the same input data, resulting in an equivalent filtering scheme. This ensures that a two-dimensional convolution will be able to be performed by a one-dimensional convolution operator as the 2D filter has been unwound to a 1D filter with gaps of zeroes separating the filter coefficients.

Assuming that some-low pass two-dimensional filter was used, such as:

<td>0

</td>

<td>-1

</td>

<td>0

</td></tr>

<tr>

<td>-1

</td>

<td>4

</td>

<td>-1

</td></tr>

<tr>

<td>0

</td>

<td>-1

</td>

<td>0

</td></tr></tbody></table>

Then, once the two-dimensional space was converted into a helix, the one-dimensional filter would look as follows:

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle h(n)=-1,0,...,0,-1,4,-1,0,...,0,-1,0,...}</annotation>

</semantics>

</math><img src="./f0c030959a15ffe9517b124f4592159c20f54c47.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:47.824ex; height:2.843ex;" alt="{\displaystyle h(n)=-1,0,...,0,-1,4,-1,0,...,0,-1,0,...}" loading="lazy">

Notice in the one-dimensional filter that there are no leading zeroes as illustrated in the one-dimensional filtering strip after being unwound. The entire one-dimensional strip could have been convolved with; however, it is less computationally expensive to simply ignore the leading zeroes. In addition, none of these backside zero values will need to be stored in memory, preserving precious memory resources.<a href="#cite_note-:2-15">[15]</a>

<div class="mw-heading mw-heading3"><h3 id="Applications">Applications</h3></div>

Helix transformations to implement recursive filters via convolution are used in various areas of signal processing. Although frequency domain Fourier analysis is effective when systems are stationary, with constant coefficients and periodically-sampled data, it becomes more difficult in unstable systems. The helix transform enables three-dimensional post-stack migration processes that can process data for three-dimensional variations in velocity.<a href="#cite_note-:2-15">[15]</a> In addition, it can be applied to assist with the problem of implicit three-dimensional wavefield extrapolation.<a href="#cite_note-16">[16]</a> Other applications include helpful algorithms in seismic data regularization, prediction error filters, and noise attenuation in geophysical digital systems.<a href="#cite_note-:1-14">[14]</a>

<div class="mw-heading mw-heading2"><h2 id="Gaussian_convolution">Gaussian convolution</h2></div>

One application of multidimensional convolution that is used within signal and image processing is Gaussian convolution. This refers to convolving an input signal with the Gaussian distribution function.

The Gaussian distribution sampled at discrete values in one dimension is given by the following (assuming <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mu =0}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mu =0}</annotation>

</semantics>

</math><img src="./3753282c0ad2ea1e7d63f39425efd13c37da3169.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.663ex; height:2.676ex;" alt="{\displaystyle \mu =0}" loading="lazy">):<math display="block" xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G(n)={\frac {1}{\sqrt {2\pi \sigma ^{2}}}}e^{-{\frac {n^{2}}{2\sigma ^{2}}}}}">

<mfrac>

<msqrt>

<msup>

</mrow>

</msup>

</msqrt>

</mfrac>

</mrow>

<msup>

<mfrac>

<msup>

</mrow>

</msup>

<mrow>

<msup>

</mrow>

</msup>

</mrow>

</mfrac>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G(n)={\frac {1}{\sqrt {2\pi \sigma ^{2}}}}e^{-{\frac {n^{2}}{2\sigma ^{2}}}}}</annotation>

</semantics>

</math>This is readily extended to a signal of M dimensions (assuming <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \sigma }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \sigma }</annotation>

</semantics>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mu _{1}=\mu _{2}=...=\mu _{M}=0}</annotation>

</semantics>

</math><img src="./03bed9de9574095d0c3236112d9bd4bb10336e68.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:23.64ex; height:2.676ex;" alt="{\displaystyle \mu _{1}=\mu _{2}=...=\mu _{M}=0}" loading="lazy">):<math display="block" xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G(n_{1},n_{2},...,n_{M})={\frac {1}{(2\pi )^{M/2}\sigma ^{M}}}e^{-{\frac {({n_{1}}^{2}+{n_{2}}^{2}+...+{n_{M}}^{2})}{2\sigma ^{2}}}}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<mfrac>

<mrow>

<msup>

</mrow>

</mrow>

</msup>

<msup>

</mrow>

</msup>

</mrow>

</mfrac>

</mrow>

<msup>

<mfrac>

<mrow>

<msup>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</msup>

<msup>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</msup>

<msup>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</msup>

</mrow>

<mrow>

<msup>

</mrow>

</msup>

</mrow>

</mfrac>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G(n_{1},n_{2},...,n_{M})={\frac {1}{(2\pi )^{M/2}\sigma ^{M}}}e^{-{\frac {({n_{1}}^{2}+{n_{2}}^{2}+...+{n_{M}}^{2})}{2\sigma ^{2}}}}}</annotation>

</semantics>

</math>One important property to recognize is that the M dimensional signal is separable such that:<math display="block" xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G(n_{1},n_{2},...,n_{M})=G(n_{1})G(n_{2})...G(n_{M})}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G(n_{1},n_{2},...,n_{M})=G(n_{1})G(n_{2})...G(n_{M})}</annotation>

</semantics>

</math>Then, Gaussian convolution with discrete-valued signals can be expressed as the following:

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y(n)=x(n)*G(n)}</annotation>

</semantics>

</math><img src="./474aa5e255392e2426e047797f495f35c094dbe0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:19.217ex; height:2.843ex;" alt="{\displaystyle y(n)=x(n)*G(n)}" loading="lazy">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y(n_{1},n_{2},...,n_{M})=x(n_{1},n_{2},...,n_{M})*...*G(n_{1},n_{2},...,n_{M})}</annotation>

</semantics>

</math><img src="./6ec067521ad253263efe1dd9967effaaee357c18.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:61.631ex; height:2.843ex;" alt="{\displaystyle y(n_{1},n_{2},...,n_{M})=x(n_{1},n_{2},...,n_{M})*...*G(n_{1},n_{2},...,n_{M})}" loading="lazy">

<div class="mw-heading mw-heading3"><h3 id="Approximation_by_FIR_filter">Approximation by FIR filter</h3></div>

Gaussian convolution can be effectively approximated via implementation of a <a href="Finite_impulse_response" title="Finite impulse response">Finite impulse response</a> (FIR) filter. The filter will be designed with truncated versions of the Gaussian. For a two-dimensional filter, the transfer function of such a filter would be defined as the following:<a href="#cite_note-:0-17">[17]</a>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<mfrac>

<mrow>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</mfrac>

</mrow>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

<msub>

</mrow>

</msub>

</mrow>

</munderover>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

<msub>

</mrow>

</msub>

</mrow>

</munderover>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msup>

<msub>

</mrow>

</msub>

</mrow>

<msub>

</mrow>

</msub>

</mrow>

</msup>

<msup>

<msub>

</mrow>

</msub>

</mrow>

<msub>

</mrow>

</msub>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle H(z_{1},z_{2})={\frac {1}{s(r_{1},r_{2})}}\sum _{n_{1}=-r_{1}}^{r_{1}}\sum _{n_{2}=-r_{2}}^{r_{2}}G(n_{1},n_{2}){z_{1}}^{-n_{1}}{z_{2}}^{-n_{2}}}</annotation>

</semantics>

</math><img src="./23c7aa670c7a2f4bd6b0017b4bba593df59051e0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.171ex; width:54.805ex; height:7.176ex;" alt="{\displaystyle H(z_{1},z_{2})={\frac {1}{s(r_{1},r_{2})}}\sum _{n_{1}=-r_{1}}^{r_{1}}\sum _{n_{2}=-r_{2}}^{r_{2}}G(n_{1},n_{2}){z_{1}}^{-n_{1}}{z_{2}}^{-n_{2}}}" loading="lazy">

where

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

<msub>

</mrow>

</msub>

</mrow>

</munderover>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

<msub>

</mrow>

</msub>

</mrow>

</munderover>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle s(r_{1},r_{2})=\sum _{n_{1}=-r_{1}}^{r_{1}}\sum _{n_{2}=-r_{2}}^{r_{2}}G(n_{1},n_{2})}</annotation>

</semantics>

</math><img src="./151de2f5ab30d26e41882a336f213bc7b0f463fd.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.171ex; width:33.476ex; height:7.176ex;" alt="{\displaystyle s(r_{1},r_{2})=\sum _{n_{1}=-r_{1}}^{r_{1}}\sum _{n_{2}=-r_{2}}^{r_{2}}G(n_{1},n_{2})}" loading="lazy">

Choosing lower values for <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle r_{1}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle r_{1}}</annotation>

</semantics>

</math><img src="./ea214f2b31fb3869344bb9311da41c5cc38a99e1.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.103ex; height:2.009ex;" alt="{\displaystyle r_{1}}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle r_{2}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle r_{2}}</annotation>

</semantics>

</math><img src="./4cbe9b0b294fdd6fadbf9a7249813f016dcbc44f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.103ex; height:2.009ex;" alt="{\displaystyle r_{2}}" loading="lazy"> will result in performing less computations, but will yield a less accurate approximation while choosing higher values will yield a more accurate approximation, but will require a greater number of computations.

<div class="mw-heading mw-heading3"><h3 id="Approximation_by_box_filter">Approximation by box filter</h3></div>

Another method for approximating Gaussian convolution is via recursive passes through a box filter. For approximating one-dimensional convolution, this filter is defined as the following:<a href="#cite_note-:0-17">[17]</a>

<mfrac>

<mrow>

</mrow>

</mfrac>

</mrow>

<mfrac>

<mrow>

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

</mrow>

<mrow>

<msup>

</mrow>

</msup>

</mrow>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle H(z)={\frac {1}{2r+1}}{\frac {z^{r}-z^{-r-1}}{1-z^{-}1}}}</annotation>

</semantics>

</math><img src="./ede0e022187409432ffde186a2a58f09fcd484bb.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.171ex; width:26.293ex; height:6.009ex;" alt="{\displaystyle H(z)={\frac {1}{2r+1}}{\frac {z^{r}-z^{-r-1}}{1-z^{-}1}}}" loading="lazy">

Typically, recursive passes 3, 4, or 5 times are performed in order to obtain an accurate approximation.<a href="#cite_note-:0-17">[17]</a> A suggested method for computing r is then given as the following:<a href="#cite_note-18">[18]</a>

<msup>

</mrow>

</msup>

<mfrac>

</mfrac>

</mrow>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \sigma ^{2}={\frac {1}{12}}K((2r+1)^{2}-1)}</annotation>

</semantics>

</math><img src="./0dbe02eaea6afed5f8de3d3bd61c65f89f5a027c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.838ex; width:25.6ex; height:5.176ex;" alt="{\displaystyle \sigma ^{2}={\frac {1}{12}}K((2r+1)^{2}-1)}" loading="lazy"> where K is the number of recursive passes through the filter.

Then, since the Gaussian distribution is separable across different dimensions, it follows that recursive passes through one-dimensional filters (isolating each dimension separately) will thus yield an approximation of the multidimensional Gaussian convolution. That is, M-dimensional Gaussian convolution could be approximated via recursive passes through the following one-dimensional filters:

<msub>

</mrow>

</msub>

<mfrac>

<mrow>

<msub>

</mrow>

</msub>

</mrow>

</mfrac>

</mrow>

<mfrac>

<mrow>

<msup>

<msub>

</mrow>

</msub>

</mrow>

<msub>

</mrow>

</msub>

</mrow>

</msup>

<msup>

<msub>

</mrow>

</msub>

</mrow>

<msub>

</mrow>

</msub>

</mrow>

</msup>

</mrow>

<mrow>

<msup>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</msup>

</mrow>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle H(z_{1})={\frac {1}{2r_{1}+1}}{\frac {{z_{1}}^{r_{1}}-{z_{1}}^{-r_{1}-1}}{1-{z_{1}}^{-}1}}}</annotation>

</semantics>

</math><img src="./4483064da476ef2d4e65df028566a6ab7970d390.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.338ex; width:32.148ex; height:6.176ex;" alt="{\displaystyle H(z_{1})={\frac {1}{2r_{1}+1}}{\frac {{z_{1}}^{r_{1}}-{z_{1}}^{-r_{1}-1}}{1-{z_{1}}^{-}1}}}" loading="lazy">

<msub>

</mrow>

</msub>

<mfrac>

<mrow>

<msub>

</mrow>

</msub>

</mrow>

</mfrac>

</mrow>

<mfrac>

<mrow>

<msup>

<msub>

</mrow>

</msub>

</mrow>

<msub>

</mrow>

</msub>

</mrow>

</msup>

<msup>

<msub>

</mrow>

</msub>

</mrow>

<msub>

</mrow>

</msub>

</mrow>

</msup>

</mrow>

<mrow>

<msup>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</msup>

</mrow>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle H(z_{2})={\frac {1}{2r_{2}+1}}{\frac {{z_{2}}^{r_{2}}-{z_{2}}^{-r_{2}-1}}{1-{z_{2}}^{-}1}}}</annotation>

</semantics>

</math><img src="./f161f35910135d00856ffc4aa6c39af2b905b7a4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.338ex; width:32.148ex; height:6.176ex;" alt="{\displaystyle H(z_{2})={\frac {1}{2r_{2}+1}}{\frac {{z_{2}}^{r_{2}}-{z_{2}}^{-r_{2}-1}}{1-{z_{2}}^{-}1}}}" loading="lazy">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \vdots }</annotation>

</semantics>

</math><img src="./f8039d9feb6596ae092e5305108722975060c083.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.647ex; height:3.676ex;" alt="{\displaystyle \vdots }" loading="lazy">

<msub>

</mrow>

</msub>

<mfrac>

<mrow>

<msub>

</mrow>

</msub>

</mrow>

</mfrac>

</mrow>

<mfrac>

<mrow>

<msup>

<msub>

</mrow>

</msub>

</mrow>

<msub>

</mrow>

</msub>

</mrow>

</msup>

<msup>

<msub>

</mrow>

</msub>

</mrow>

<msub>

</mrow>

</msub>

</mrow>

</msup>

</mrow>

<mrow>

<msup>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</msup>

</mrow>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle H(z_{M})={\frac {1}{2r_{M}+1}}{\frac {{z_{M}}^{r_{M}}-{z_{M}}^{-r_{M}-1}}{1-{z_{M}}^{-}1}}}</annotation>

</semantics>

</math><img src="./2096b4789f2368699f8076d1678878ba388bb74f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.338ex; width:37.237ex; height:6.176ex;" alt="{\displaystyle H(z_{M})={\frac {1}{2r_{M}+1}}{\frac {{z_{M}}^{r_{M}}-{z_{M}}^{-r_{M}-1}}{1-{z_{M}}^{-}1}}}" loading="lazy">

<div class="mw-heading mw-heading3"><h3 id="Applications_2">Applications</h3></div>

Gaussian convolutions are used extensively in signal and image processing. For example, image-blurring can be accomplished with Gaussian convolution where the <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \sigma }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \sigma }</annotation>

</semantics>

</math><img src="./59f59b7c3e6fdb1d0365a494b81fb9a696138c36.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.33ex; height:1.676ex;" alt="{\displaystyle \sigma }" loading="lazy"> parameter will control the strength of the blurring. Higher values would thus correspond to a more blurry end result.<a href="#cite_note-19">[19]</a> It is also commonly used in <a href="Computer_vision" title="Computer vision">Computer vision</a> applications such as <a href="Scale-invariant_feature_transform" title="Scale-invariant feature transform">Scale-invariant feature transform</a> (SIFT) feature detection.<a href="#cite_note-20">[20]</a>

<ul><li><a href="Convolution" title="Convolution">Convolution</a></li>

<li><a href="Kernel_(image_processing)" title="Kernel (image processing)">Kernel (image processing)</a></li>

<li><a href="Signal_processing" title="Signal processing">Signal processing</a></li></ul>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}

/* end https://en.wikipedia.org/ */

</style><div class="reflist reflist-columns references-column-width" style="column-width: 30em;">

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><cite id="CITEREFDudgeonMersereau1983" class="citation cs2">Dudgeon, Dan; Mersereau, Russell (1983), Multidimensional Digital Signal Processing, Prentice-Hall, pp. 21–22</cite>

</li>

<li id="cite_note-2"><a href="#cite_ref-2">^</a> <cite class="citation web cs1"><a rel="nofollow" class="external text" href="http://homepages.inf.ed.ac.uk/rbf/CVonline/LOCAL_COPIES/MARBLE/">"MARBLE: Interactive Vision"</a>. homepages.inf.ed.ac.uk. Retrieved 2015-11-12.</cite>

</li>

<li id="cite_note-3"><a href="#cite_ref-3">^</a> <cite class="citation web cs1"><a rel="nofollow" class="external text" href="http://www-rohan.sdsu.edu/~jiracek/DAGSAW/4.1.html">"Digital Geophysical Analysis Redesign"</a>. www-rohan.sdsu.edu. Retrieved 2015-11-12.</cite>

</li>

<li id="cite_note-4"><a href="#cite_ref-4">^</a> <cite id="CITEREFSihvoNiittylahti2005" class="citation book cs1">Sihvo, Tero; Niittylahti, Jarkko (5 June 2005). "Row-Column Decomposition Based 2D Transform Optimization on Subword Parallel Processors". International Symposium on Signals, Circuits and Systems, 2005. ISSCS 2005. Vol. 1. pp. 99–102. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1109%2FISSCS.2005.1509860">10.1109/ISSCS.2005.1509860</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-0-7803-9029-4</bdi>.</cite>

</li>

<li id="cite_note-5"><a href="#cite_ref-5">^</a> <cite class="citation web cs1"><a rel="nofollow" class="external text" href="http://www.cs.umd.edu/class/sum2003/cmsc311/Notes/Memory/introCache.html">"Introduction to Caches"</a>. Computer Science University of Maryland. Retrieved 10 November 2015.</cite>

</li>

<li id="cite_note-6"><a href="#cite_ref-6">^</a> <cite id="CITEREFEddins" class="citation web cs1">Eddins, Steve. <a rel="nofollow" class="external text" href="http://blogs.mathworks.com/steve/2006/10/04/separable-convolution/">"Separable Convolution"</a>. Mathwords. Retrieved 10 November 2015.</cite>

</li>

<li id="cite_note-7"><a href="#cite_ref-7">^</a> <cite id="CITEREFDudgeonMersereau1983" class="citation cs2">Dudgeon, Dan; Mersereau, Russell (1983), Multidimensional Digital Signal Processing, Prentice-Hall, p. 70</cite>

</li>

<li id="cite_note-8"><a href="#cite_ref-8">^</a> <cite id="CITEREFDudgeonMersereau1983" class="citation cs2">Dudgeon, Dan; Mersereau, Russell (1983), Multidimensional Digital Signal Processing, Prentice-Hall, p. 72</cite>

</li>

<li id="cite_note-9"><a href="#cite_ref-9">^</a> <cite id="CITEREFFernandezKumar2013" class="citation book cs1">Fernandez, Joseph; Kumar, Vijaya (2013). Multidimensional Overlap-Add and Overlap-Save for Correlation and Convolution. pp. 509–513. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1109%2FICIP.2013.6738105">10.1109/ICIP.2013.6738105</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-1-4799-2341-0</bdi>.</cite>

</li>

<li id="cite_note-10"><a href="#cite_ref-10">^</a> <cite class="citation web cs1"><a rel="nofollow" class="external text" href="http://www.eeng.dcu.ie/~ee502/EE502s4.pdf">"2D Signal Processing"</a> (PDF). EE502: Digital Signal Processing. Dublin City University. p. 24. Retrieved November 11, 2015.</cite>

</li>

<li id="cite_note-:3-11">^ <a href="#cite_ref-:3_11-0">a</a> <a href="#cite_ref-:3_11-1">b</a> <cite id="CITEREFKundur" class="citation web cs1">Kundur, Deepa. <a rel="nofollow" class="external text" href="http://www.comm.utoronto.ca/~dkundur/course_info/real-time-DSP/notes/8_Kundur_Overlap_Save_Add.pdf">"Overlap-Save and Overlap-Add"</a> (PDF). University of Toronto. Retrieved November 12, 2015.</cite>

</li>

<li id="cite_note-12"><a href="#cite_ref-12">^</a> <cite class="citation web cs1"><a rel="nofollow" class="external text" href="http://www.eeng.dcu.ie/~ee502/EE502s4.pdf">"2D Signal Processing"</a> (PDF). EE502: Digital Signal Processing. Dublin City University. p. 26. Retrieved November 11, 2015.</cite>

</li>

<li id="cite_note-13"><a href="#cite_ref-13">^</a> <cite id="CITEREFKimStrintzis1980" class="citation journal cs1 cs1-prop-long-vol">Kim, Chang; Strintzis, Michael (May 1980). "High-Speed Multidimensional Convolution". IEEE Transactions on Pattern Analysis and Machine Intelligence. PAMI-2 (3): 269–273. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1109%2Ftpami.1980.4767017">10.1109/tpami.1980.4767017</a>.</cite>

</li>

<li id="cite_note-:1-14">^ <a href="#cite_ref-:1_14-0">a</a> <a href="#cite_ref-:1_14-1">b</a> <cite id="CITEREFNaghizadehSacchi2009" class="citation journal cs1">Naghizadeh, Mostafa; Sacchi, Mauricio (November 2009). <a rel="nofollow" class="external text" href="https://www.researchgate.net/publication/274360447">"Multidimensional convolution via a 1D convolution algorithm"</a>. The Leading Edge.</cite>

</li>

<li id="cite_note-:2-15">^ <a href="#cite_ref-:2_15-0">a</a> <a href="#cite_ref-:2_15-1">b</a> <cite id="CITEREFClaerbout1998" class="citation journal cs1">Claerbout, Jon (September 1998). "Multidimensional recursive filters via a helix". Geophysics. 63 (5): 9. <a href="Bibcode_(identifier)" class="mw-redirect" title="Bibcode (identifier)">Bibcode</a>:<a rel="nofollow" class="external text" href="https://ui.adsabs.harvard.edu/abs/1998Geop...63.1532C">1998Geop...63.1532C</a>. <a href="CiteSeerX_(identifier)" class="mw-redirect" title="CiteSeerX (identifier)">CiteSeerX</a> <a rel="nofollow" class="external text" href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.76.1193">10.1.1.76.1193</a>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1190%2F1.1444449">10.1190/1.1444449</a>.</cite>

</li>

<li id="cite_note-16"><a href="#cite_ref-16">^</a> <cite id="CITEREFFomelClaerbout1997" class="citation journal cs1">Fomel, Sergey; Claerbout, Jon (1997). <a rel="nofollow" class="external text" href="https://web.archive.org/web/20190104124207/https://pdfs.semanticscholar.org/5993/a76fdb37d3b1a3dfba795d6ed596c608cec9.pdf">"Exploring three-dimensional implicit wavefield extrapolation with the helix transform"</a> (PDF). SEP Report: 43–60. Archived from <a rel="nofollow" class="external text" href="https://pdfs.semanticscholar.org/5993/a76fdb37d3b1a3dfba795d6ed596c608cec9.pdf">the original</a> (PDF) on 2019-01-04.</cite>

</li>

<li id="cite_note-:0-17">^ <a href="#cite_ref-:0_17-0">a</a> <a href="#cite_ref-:0_17-1">b</a> <a href="#cite_ref-:0_17-2">c</a> <cite id="CITEREFGetreuer2013" class="citation journal cs1">Getreuer, Pascal (2013). <a rel="nofollow" class="external text" href="https://doi.org/10.5201%2Fipol.2013.87">"A Survey of Gaussian Convolution Algorithms"</a>. Image Processing on Line. 3: 286–310. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.5201%2Fipol.2013.87">10.5201/ipol.2013.87</a>.</cite>

</li>

<li id="cite_note-18"><a href="#cite_ref-18">^</a> <cite id="CITEREFWells1986" class="citation journal cs1 cs1-prop-long-vol">Wells, W.M. (1986). "Efficient synthesis of Gaussian filters by cascaded uniform filters". IEEE Transactions on Pattern Analysis and Machine Intelligence. PAMI-8 (2): 234–239. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1109%2FTPAMI.1986.4767776">10.1109/TPAMI.1986.4767776</a>.</cite>

</li>

<li id="cite_note-19"><a href="#cite_ref-19">^</a> <cite class="citation web cs1"><a rel="nofollow" class="external text" href="http://patrick-fuller.com/gaussian-blur-image-processing-for-scientists-and-engineers-part-4/">"Gaussian Blur - Image processing for scientists and engineers, Part 4"</a>. patrick-fuller.com. Retrieved 2015-11-12.</cite>

</li>

<li id="cite_note-20"><a href="#cite_ref-20">^</a> <cite id="CITEREFLowe1999" class="citation journal cs1">Lowe, D.G. (1999). <a rel="nofollow" class="external text" href="http://www.cs.ubc.ca/~lowe/papers/iccv99.pdf">"Object recognition from local scale-invariant features"</a> (PDF). Proceedings of the International Conference on Computer Vision. 2: 1150–1157.</cite>

</li>

</ol></div></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2025-06-14" href="https://en.wikipedia.org/wiki/?title=Multidimensional_discrete_convolution&oldid=1295516739">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>